TreesTrees

Binary Tree Traversals

A hierarchical structure where every node has at most two children, the foundation of BSTs, heaps and expression trees.

Level-order values | traversal — Level-order list with "null" for gaps, then a pipe and inorder | preorder | postorder | levelorder

inorder output

empty

1/27Start a inorder traversal at the root 1. The output list on the right fills as nodes are visited.

Node being processedOn the call stackAlready output

PseudocodeLearn Binary Tree →

1traverse(node):
2  if node is null: return
3  [preorder]  visit(node)
4  traverse(node.left)
5  [inorder]   visit(node)
6  traverse(node.right)
7  [postorder] visit(node)
8levelorder: queue = [root]
9  while queue: node = queue.popleft(); visit(node); push node.left, node.right

Variables

orderinorder

nodes6

Complexity

access O(n)

search O(n)

insert O(n)

delete O(n)

Speed