BST Traversal
Basically, there are three methods of tree traversal: pre-order, in-order, and post-order traversal. The difference between the three methods is in the order of elements. Let's see how we achieve this in code.
In this chapter we will work with the following tree:
![](https://codefinity-content-media.s3.eu-west-1.amazonaws.com/212d3d3e-af15-4df9-bb13-5cbbb8114954/tree_transparent.png)
The pre-order traversal
The pre-order traversal yields the natural ordering. First, we visit the root node and then recursively each subtree's left and right subtrees.
We put the append
statement before the recursive calls to achieve this.
The in-order traversal
The in-order traversal is probably the most common, as it yields the sorted order of the elements in the tree.
When implementing an in-order traversal, we put the append
statement in the middle between two recursive calls on the left and the right subtrees.
The post-order traversal
The third way to traverse a Binary Search Tree is to use the post-order traversal. The post-order traversal algorithm first visits the left and the right subtree and then visits the root node for each subtree in the initial tree.
We append the nodes after the recursive calls to implement the post-order traversal.
¿Todo estuvo claro?
Contenido del Curso
Algorithms and Data Structures Overview
Algorithms and Data Structures Overview
BST Traversal
Basically, there are three methods of tree traversal: pre-order, in-order, and post-order traversal. The difference between the three methods is in the order of elements. Let's see how we achieve this in code.
In this chapter we will work with the following tree:
![](https://codefinity-content-media.s3.eu-west-1.amazonaws.com/212d3d3e-af15-4df9-bb13-5cbbb8114954/tree_transparent.png)
The pre-order traversal
The pre-order traversal yields the natural ordering. First, we visit the root node and then recursively each subtree's left and right subtrees.
We put the append
statement before the recursive calls to achieve this.
The in-order traversal
The in-order traversal is probably the most common, as it yields the sorted order of the elements in the tree.
When implementing an in-order traversal, we put the append
statement in the middle between two recursive calls on the left and the right subtrees.
The post-order traversal
The third way to traverse a Binary Search Tree is to use the post-order traversal. The post-order traversal algorithm first visits the left and the right subtree and then visits the root node for each subtree in the initial tree.
We append the nodes after the recursive calls to implement the post-order traversal.
¿Todo estuvo claro?