Trees & Binary Search Trees

Q: What is Morris In-Order Traversal?

Morris Traversal uses threaded binary trees (temporarily pointing the rightmost node of the left subtree to the current node) to achieve in-order traversal in O(N) time without using ANY stack or recursion space (true O(1) auxiliary space).

Hierarchical data modeling: recursive DFS traversals (preorder, inorder, postorder), queue-based level order BFS, BST search/insert invariants, and binary heaps.

Hierarchical Nodes & The BST Invariant

A Tree is a non-linear hierarchical data structure consisting of nodes connected by directed edges without cycles. A Binary Search Tree (BST) enforces the fundamental ordering property: for every node, all keys in its left subtree are strictly less, and all keys in its right subtree are strictly greater.

BST Inorder Traversal Property:An In-Order DFS traversal (Left -> Node -> Right) of a valid BST ALWAYS produces a strictly monotonically increasing sorted array.
Search & Insertion Complexity:Average O(log N) in balanced trees (AVL, Red-Black); degrades to O(N) in skewed/degenerate trees.
Tree Traversals (DFS vs BFS):DFS uses call-stack/explicit stack (Preorder: N-L-R, Inorder: L-N-R, Postorder: L-R-N); BFS uses a FIFO queue for Level-Order traversal.

Validating BST with Strict Upper/Lower Bounds: Never just check node.left.val < node.val. You must propagate strict valid ranges down the tree: validate(node, min_val, max_val) where left child must satisfy (min_val, node.val) and right child satisfies (node.val, max_val).
Lowest Common Ancestor (LCA) in BST: If both p and q are smaller than curr.val, move left; if both are larger, move right; the first node where p and q split across left/right (or match curr) is the LCA in O(H) time!
Level-Order BFS Traversal: Push root into a Queue. While queue is non-empty, record level_size = len(queue) and process exactly level_size nodes in a inner loop to separate tree levels.

Related references:Graph Traversal BFS/DFS Binary Search Mastery

Definition: Lowest Common Ancestor (LCA)

The deepest node in a tree that has both node p and node q as descendants (where a node is permitted to be a descendant of itself).

Tree Height vs Node Count Relation

Balanced Tree Height: H = floor(log2(N)) ==> Max Nodes: 2^(H+1) - 1

Variable Definitions & Term Breakdown:

NTotal number of nodes in the binary tree

HHeight of the tree (length of longest root-to-leaf path)

Binary Tree Traversals Comparison

Traversal Type	Node Visit Sequence	Data Structure	Typical Application
Pre-Order DFS	Node -> Left -> Right	Call Stack	Tree Serialization & Cloning
In-Order DFS	Left -> Node -> Right	Call Stack	Sorted BST Output
Post-Order DFS	Left -> Right -> Node	Call Stack	Bottom-Up Deletion & Subtree Height Calculation
Level-Order BFS	Level by Level	FIFO Queue	Shortest Path & Level Averages

Order, underlying data structure, and primary use cases

Tip

When solving subtree diameter, maximum path sum, or tree balance problems, compute the node's property during Post-Order return (bottom-up) rather than computing top-down to avoid quadratic O(N^2) repeated subtree recalculations.

PythonBST Validation with Min/Max Bounds Sandbox

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6 
7def is_valid_bst(root: TreeNode) -> bool:
8    def validate(node, low=float('-inf'), high=float('inf')):
9        if not node:
10            return True
11        if not (low < node.val < high):
12            return False
13        return (
14            validate(node.left, low, node.val) and
15            validate(node.right, node.val, high)
16        )
17    return validate(root)
18 
19# Construct Valid BST: [2, 1, 3]
20tree_valid = TreeNode(2, TreeNode(1), TreeNode(3))
21# Construct Invalid BST: [5, 1, 4, null, null, 3, 6] (4 has child 3 which is < 5)
22tree_invalid = TreeNode(5, TreeNode(1), TreeNode(4, TreeNode(3), TreeNode(6)))
23 
24print('Tree 1 is Valid BST?', is_valid_bst(tree_valid))
25print('Tree 2 is Valid BST?', is_valid_bst(tree_invalid))

Output

Tree 1 is Valid BST? True
Tree 2 is Valid BST? False

C++C++ Lowest Common Ancestor in Binary Search Tree

1struct TreeNode {
2    int val;
3    TreeNode *left;
4    TreeNode *right;
5    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
6};
7 
8TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
9    TreeNode* curr = root;
10    while (curr) {
11        if (p->val < curr->val && q->val < curr->val) {
12            curr = curr->left;
13        } else if (p->val > curr->val && q->val > curr->val) {
14            curr = curr->right;
15        } else {
16            return curr;
17        }
18    }
19    return nullptr;
20}

Output

[Returns LCA node in O(Height) time and O(1) space]

Quick Syntax & Reference Sheet

Concept / Rule	Syntax / Usage
BST Invariant	`validate(node.left, low, node.val) and validate(node.right, node.val, high)`
BFS Level Order	`queue = deque([root]); while queue: for _ in range(len(queue)): node = queue.popleft()`
LCA in BST	`if p.val < root.val and q.val < root.val: return lca(root.left, p, q)`

Common Pitfalls & Developer Mistakes

✕ Mistake 1:

Only checking direct children in BST validation (node.left.val < node.val)

Why it happens: A node in the right subtree could be smaller than the root ancestor, violating global BST invariant.

Correction: Always pass min_val and max_val bounds down recursive calls.

# Correct:
validate(node.left, min_bound, node.val)
validate(node.right, node.val, max_bound)

Frequently Asked Questions

What is Morris In-Order Traversal?

Morris Traversal uses threaded binary trees (temporarily pointing the rightmost node of the left subtree to the current node) to achieve in-order traversal in O(N) time without using ANY stack or recursion space (true O(1) auxiliary space).