BST Traversal Techniques
In a Binary Search Tree (BST), traversal refers to visiting each node in a specific order. There are three main types of depth-first traversal techniques:
1. Inorder Traversal
Inorder traversal visits the nodes in the order: Left Subtree → Root → Right Subtree.
In a Binary Search Tree (BST), this traversal returns the nodes in ascending sorted order.
Step-by-Step Algorithm
- Step 1: Traverse the left subtree recursively.
- Step 2: Visit (process) the current node.
- Step 3: Traverse the right subtree recursively.
Code
java
// class TreeNode {
// int val; // Value stored in the node
// TreeNode left; // Pointer to left child
// TreeNode right; // Pointer to right child
// // Constructor to initialize a node
// TreeNode(int val) {
// this.val = val;
// this.left = null;
// this.right = null;
// }
// }
class Solution {
// Recursive method for inorder traversal
void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left); // Traverse left subtree
System.out.print(root.val + " "); // Visit current node
inorder(root.right); // Traverse right subtree
}
public static void main(String[] args) {
// Create a sample BST:
// 8
// / \
// 3 10
// / \ \
// 1 6 14
// /
// 4
TreeNode root = new TreeNode(8);
root.left = new TreeNode(3);
root.right = new TreeNode(10);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(6);
root.left.right.left = new TreeNode(4);
root.right.right = new TreeNode(14);
Solution it = new Solution();
System.out.println("Inorder Traversal (Sorted Order):");
it.inorder(root); // Expected output: 1 3 4 6 8 10 14
}
}
Complexity Analysis
- Time Complexity:
, where n is the number of nodes (each node is visited once). - Space Complexity:
due to recursion, where h is the height of the tree (O(n) in worst-case, O(log n) for balanced BST).
2. Preorder Traversal
Preorder traversal visits nodes in the order: Root → Left Subtree → Right Subtree.
This method is useful for cloning trees or for generating a prefix expression from an expression tree.
Step-by-Step Algorithm
- Step 1: Visit (process) the current node.
- Step 2: Traverse the left subtree recursively.
- Step 3: Traverse the right subtree recursively.
Code
java
// class TreeNode {
// int val;
// TreeNode left;
// TreeNode right;
// TreeNode(int val) {
// this.val = val;
// this.left = null;
// this.right = null;
// }
// }
class Solution {
// Recursive method for preorder traversal
void preorder(TreeNode root) {
if (root == null) return;
System.out.print(root.val + " "); // Visit current node
preorder(root.left); // Traverse left subtree
preorder(root.right); // Traverse right subtree
}
public static void main(String[] args) {
// Create a sample BST:
// 8
// / \
// 3 10
// / \ \
// 1 6 14
// /
// 4
TreeNode root = new TreeNode(8);
root.left = new TreeNode(3);
root.right = new TreeNode(10);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(6);
root.left.right.left = new TreeNode(4);
root.right.right = new TreeNode(14);
Solution pt = new Solution();
System.out.println("Preorder Traversal (Root First):");
pt.preorder(root); // Expected output: 8 3 1 6 4 10 14
}
}
Complexity Analysis
- Time Complexity:
, as each node is processed once. - Space Complexity:
, where h is the height of the tree, due to recursion (worst-case O(n) in skewed trees, O(log n) in balanced trees).
3. Postorder Traversal
Postorder traversal visits nodes in the order: Left Subtree → Right Subtree → Root.
This approach is useful for deleting trees or evaluating postfix expressions.
Step-by-Step Algorithm
- Step 1: Traverse the left subtree recursively.
- Step 2: Traverse the right subtree recursively.
- Step 3: Visit (process) the current node.
Code
java
// class TreeNode {
// int val;
// TreeNode left;
// TreeNode right;
// TreeNode(int val) {
// this.val = val;
// this.left = null;
// this.right = null;
// }
// }
class Solution {
// Recursive method for postorder traversal
void postorder(TreeNode root) {
if (root == null) return;
postorder(root.left); // Traverse left subtree
postorder(root.right); // Traverse right subtree
System.out.print(root.val + " "); // Visit current node
}
public static void main(String[] args) {
// Create a sample BST:
// 8
// / \
// 3 10
// / \ \
// 1 6 14
// /
// 4
TreeNode root = new TreeNode(8);
root.left = new TreeNode(3);
root.right = new TreeNode(10);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(6);
root.left.right.left = new TreeNode(4);
root.right.right = new TreeNode(14);
Solution pt = new Solution();
System.out.println("Postorder Traversal (Root Last):");
pt.postorder(root); // Expected output: 1 4 6 3 14 10 8
}
}
Complexity Analysis
- Time Complexity:
, since each node is visited once. - Space Complexity:
, where h is the height of the tree due to recursion (worst-case O(n) in skewed trees, O(log n) in balanced trees).
🤖 Don't fully get this? Learn it with Claude
Stuck on BST Traversal Techniques? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
🎨 Explain it visually
Build the mental picture, not memorization.
I just read a lesson on **BST Traversal Techniques** (DSA) and want to truly understand it. Explain BST Traversal Techniques from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)
Socratic — adapts to where you're stuck.
Teach me **BST Traversal Techniques** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps
Active recall exposes what you missed.
Quiz me on **BST Traversal Techniques** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick
Intuition + hook + flashcards for long-term memory.
Help me remember **BST Traversal Techniques** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.