There are several ways to traverse a tree: recursive traversal, non-recursive depth-first traversal, and non-recursive breadth-first traversal.

As shown above, object can be represented in JavaScript as follows:

let tree = {
  value: 10.children: [{value: 15.children: [{value: 7.children: []}, {value: 18.children: []}]}, {value: 4.children: []}, {value: 8.children: [{value: 23.children: []}]}]};Copy the code

The recursive traversal

const recursiveTraverse = function(node, action) {
	if(! node || ! node.children) {return; } action(node.value); node.children.forEach(function(item, index) {
		recursiveTraverse(item, action)
	})
}

recursiveTraverse(tree, console.info)
// Output result:
10
15
7
18
4
8
23
Copy the code

Non-recursive depth-first traversal (with stack implementation)

const nonRecursiveDepthFirstTraversal = function (node, action) {
	if(! node || ! node.children) {return; }
	let _stack = []; // use a stack
	_stack.unshift(node);
	while (_stack.length) {
		let _curNode = _stack.shift(); // Push out the top element
		action(_curNode.value);
		// Place the child nodes at the top of the stack
		// _curNode.children.forEach(function (item, index) {
		// _stack.unshift(item);
		// })
		if(_curNode.children.length) { _stack = _curNode.children.concat(_stack); }}}// Non-recursive depth-first traversal
nonRecursiveDepthFirstTraversal(tree, console.log);

// Output result:
10
15
7
18
4
8
23
Copy the code

Non-recursive breadth-first traversal (with queue implementation)

const nonRecursiveWidthFirstTraversal = function (node, action) {
	if(! node || ! node.children) {return; }
	let _queue = []; // use a queue
	_queue.push(node);
	while (_queue.length) {
		let _curNode = _queue.shift(); // Push out the team head element
		action(_curNode.value);
		// Push the children into the queue in turn
		// _curNode.children.forEach(function (item, index) {
		// _queue.push(item);
		// })
		if(_curNode.children.length) { _queue = _queue.concat(_curNode.children); }}}// non-recursive width first traversal
nonRecursiveWidthFirstTraversal(tree, console.log);
// Output result:
10
15
4
8
7
18
23
Copy the code