Tree Traversals
Tree traversal means visiting every node in a specific order. There are three main depth-first traversals: inorder, preorder, and postorder.
1. Inorder Traversal (Left, Root, Right)
Visits left subtree, then node, then right subtree. For BST, this yields nodes in sorted order.
public void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
2. Preorder Traversal (Root, Left, Right)
Visits node, then left subtree, then right subtree. Used for copying a tree.
public void preorder(TreeNode root) {
if (root == null) return;
System.out.print(root.val + " ");
preorder(root.left);
preorder(root.right);
}
3. Postorder Traversal (Left, Right, Root)
Visits left, right, then node. Used for deleting a tree (children before parent).
public void postorder(TreeNode root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.val + " ");
}
Two Minute Drill
- Inorder: left → node → right. Sorted order for BST.
- Preorder: node → left → right. Used for copying.
- Postorder: left → right → node. Used for deletion.
- All are O(n) time and O(h) stack space (recursive).
Need more clarification?
Drop us an email at career@quipoinfotech.com