BST In Order Traversal
BST Construction is covered here.
Sample tree:
5
/ \
2 9
/ \ \
1 3 10In Order traversal
The root element will be between the left and the right elements respectively.
[1, 2, 3, 5, 9, 10]
Note: In order traversal of a BST results in a sorted list.
Recursive solution:
var traversal = []
function preorder(root) {
if (root == null) return
preorder(root.left)
traversal.push(root.val)
preorder(root.right)
}Iterative solution:
Depth first search, using a stack.
var traversal = []
var stack = []
while (stack.length != 0 || root != null) {
while (root != null) {
stack.push(root)
root = root.left
}
var node = stack.pop()
traversal.push(node.val)
root = node.right
}