As mentioned before, there are different ways to visit all the nodes or search for a value in a binary tree. On this section, we are going to focus on depth-first tree traversal.
If your tree happens to be a binary search tree (BST), then you can use "in order" traversal to get the values sorted in ascending order. To accomplish this, you have to visit the nodes in a left-root-right order.
If we have the following tree:
10
/ \
5 30
/ / \
4 15 40
/
3
In-order traverval will return 3, 4, 5, 10, 15, 30, 40.
Check out the implementation:
link:../../../src/data-structures/trees/binary-search-tree.js[role=include]This function goes recursively to the leftmost element and then yield that node, then we go to the right child (if any) and repeat the process. This method will get us the values ordered.
Pre-order traversal visits nodes in this order root-left-right recursively.
-
Create a copy of the tree.
-
Get prefix expression on of an expression tree used in the polish notation.
link:../../../src/data-structures/trees/binary-search-tree.js[role=include]If we have the following tree:
10
/ \
5 30
/ / \
4 15 40
/
3
Pre-order traverval will return 10, 5, 4, 3, 30, 15, 40.
Post-order traversal goes to each node in this order left-right-root recursively.
-
Traversal is used to delete the tree because you visit the children before removing the parent.
-
Get the postfix expression of an expression tree used in the reverse polish notation.
link:../../../src/data-structures/trees/binary-search-tree.js[role=include]If we have the following tree:
10
/ \
5 30
/ / \
4 15 40
/
3
Post-order traverval will return 3, 4, 5, 15, 40, 30, 10.