Source: UIUC Data Structures
Tags: BST search sequence, valid search path, expression tree, infix, prefix, postfix, remove complexity, height function, O(h), O(n), time complexity
Difficulty: Intermediate Prerequisites: BST Insert and Delete (Part 1), Binary Tree Properties and Traversals (Part 2).
Big picture
This final set covers three areas that build on the first two. First, how to validate whether a sequence of nodes could be a legitimate BST search path, a question type that tests your understanding of the BST invariant at a deeper level than simple insertion. Second, expression trees, which tie together traversal orders with arithmetic notation. Third, the time complexity of BST operations, particularly remove() and height(), which are common analysis questions on the exam.
A search path through a BST must respect all ancestor constraints, not just the immediate parent. Expression trees represent arithmetic using operators as internal nodes and operands as leaves; inorder gives infix, preorder gives prefix, and postorder gives postfix. BST remove() runs in O(h) total. Computing the height of a tree requires visiting every node, so it runs in O(n), not O(h).
Valid BST search sequence
A sequence of node values encountered when searching for a target in a BST. At each step, the search goes left (target is smaller) or right (target is larger), and all subsequent nodes must fall within the range implied by every ancestor visited so far. In simple terms, going left of a node means everything afterwards must be smaller than that node, and going right means everything afterwards must be larger.
Expression tree
A binary tree that represents an arithmetic expression. Internal nodes hold operators (+, −, ×, ÷), and leaf nodes hold operands (numbers). Think of it as a way to remove the ambiguity of operator precedence by encoding the structure directly in the tree shape.
Infix notation
The standard way humans write expressions: operand, operator, operand (e.g. 3 + 5). Produced by inorder traversal of an expression tree.
Prefix notation (Polish notation)
Operator comes before its operands (e.g. + 3 5). Produced by preorder traversal of an expression tree.
Postfix notation (Reverse Polish notation)
Operator comes after its operands (e.g. 3 5 +). Produced by postorder traversal of an expression tree.
A BST with keys between 1 and 1000 exists, but you do not know its shape. You are given a sequence of nodes visited while searching for 363. The question: could this sequence be a valid search path?
The technique: at every step, track the running constraints on the remaining values.
Valid example: 925, 202, 911, 240, 910, 245, 363
Start at 925. 363 < 925, go left. All remaining nodes must be < 925.
Visit 202. 363 > 202, go right. All remaining must be > 202 and < 925.
Visit 911. 363 < 911, go left. All remaining must be > 202 and < 911.
Visit 240. 363 > 240, go right. All remaining must be > 240 and < 911.
Visit 910. 363 < 910, go left. All remaining must be > 240 and < 910.
Visit 245. 363 > 245, go right. All remaining must be > 245 and < 910.
Visit 363. Found. Valid.
Every node respected the accumulated bounds, so this is a valid search path.
Invalid example: 2, 399, 387, 219, 266, 382, 381, 278, 401
Start at 2. 363 > 2, go right. All remaining must be > 2.
Visit 399. 363 < 399, go left. All remaining must be > 2 and < 399.
Visit 387. 363 < 387, go left. All remaining must be > 2 and < 387.
Visit 219. 363 > 219, go right. All remaining must be > 219 and < 387.
Visit 266. 363 > 266, go right. All remaining must be > 266 and < 387.
Visit 382. 363 < 382, go left. All remaining must be > 266 and < 382.
Visit 381. 363 < 381, go left. All remaining must be > 266 and < 381.
Visit 278. 363 > 278, go right. All remaining must be > 278 and < 381.
Visit 401. 401 > 381. Violates the upper bound. Invalid.
The value 401 is in the left subtree of 381 (went left from 382 to reach this branch), so everything here must be < 381. Since 401 > 381, this path is impossible in any BST.
Another invalid example: 925, 202, 911, 240, 912
After visiting 240, bounds are > 240 and < 911.
912 > 911. Violates the upper bound. Invalid.
The key insight: you must track both the lower and upper bounds as they narrow with each comparison. A single violation anywhere in the sequence makes the entire path invalid.
In an expression tree, operators (+, −, ×) have exactly two children. The unary minus (−) has only a right child. Leaf nodes are integers or variables.
Reconstructing from preorder output
Given preorder: × + 8 + 6 3 × 9 + 2 − 3
Preorder prints root first. So the root is ×. Since × has two children, the next portion is the left subtree and the rest is the right subtree.
Building the tree step by step:
Root: × (two children)
Left child of ×: + (two children)
Left child of +: 8 (leaf)
Right child of +: + (two children)
Left child: 6 (leaf)
Right child: 3 (leaf)
Right child of ×: × (two children)
Left child of ×: 9 (leaf)
Right child of ×: + (two children)
Left child of +: 2 (leaf)
Right child of +: − (only right child)
Right child of −: 3 (leaf)
Inorder traversal of this tree: 8 + 6 + 3 × 9 × 2 + − 3
Note: inorder of an expression tree gives infix notation, but without parentheses it can be ambiguous. The tree structure itself encodes the correct precedence.
In a BST, the minimum is always the leftmost node (follow left pointers from the root). This takes O(h) time.
In a general binary tree (no ordering property), there is no shortcut. Any node could hold the minimum value, so you must check every node. Any traversal works. Time: O(n).
The remove operation is implemented as: find the key, then remove the node.
Step 1: find(key) runs in O(h). At each level, compare and move left or right. At most h comparisons.
Step 2: determine how many children the node has. O(1). You have a pointer to the node, so checking whether left and right children are NULL is constant time.
Step 3: perform the removal.
0 children: set parent's pointer to NULL. O(1).
1 child: redirect parent's pointer to the node's child. O(1).
2 children: find IOP or IOS (O(h) time, as you traverse down from the node). Swap keys (O(1)). Then remove the swapped node, which now has 0 or 1 children (O(1)).
Total worst case: O(h) for find + O(h) for IOP/IOS + O(1) for the actual removal = O(h).
The height function computes the height of a tree recursively:
height(root):
if root is NULL: return -1
return max(height(root.left), height(root.right)) + 1
At each node, the function does O(1) work (a comparison and an addition). The function is called once on every node in the tree, because the recursive calls walk through the entire left and right subtrees.
A tree with n nodes has n subtrees, each rooted at a specific node. Each node gets height() called on it exactly once (by its parent). Therefore the total number of calls is n, plus the NULL base cases.
Total time: O(n), not O(h).
This is a common trap. Students see "height" and think O(h), but computing the height requires visiting every node to find the deepest path, so it must be O(n).
BST remove() total time: O(h) = O(h) find + O(h) IOP/IOS + O(1) delete
height() total time: O(n) = O(1) per node × n nodes
height(root) = max(height(root.left), height(root.right)) + 1
height(NULL) = -1 (base case)
Expression trees are the internal representation compilers use for arithmetic expressions. When your compiler optimises (a + b) * (c - d), it is manipulating an expression tree, reordering and simplifying subtrees.
BST search validation logic is analogous to range checks in database query optimisers. When a query engine narrows down which index pages to visit, it tracks upper and lower key bounds much the same way.
Students frequently answer O(h) for the runtime of height(). The function must visit every node to determine the maximum depth, so it is O(n). O(h) would only be correct if you already knew which path was longest and just needed to walk it.
Students sometimes think a search sequence is valid if each consecutive pair respects parent-child ordering. This is not enough. You must check that every value respects the accumulated bounds from all ancestors, not just the immediate parent.
Students occasionally assume postorder notation is the same as "reverse preorder." It is not. Postorder visits left, right, root. Reversing preorder would give right, left, root, which is different.
When validating search sequences, students forget to update both bounds. Going left tightens the upper bound; going right tightens the lower bound. Both must be tracked.
⚠️ Search sequence validation questions test deep understanding of the BST invariant. Practise tracking upper and lower bounds by hand.
⚠️ The height() runtime (O(n), not O(h)) is a very common trick question. Be ready to explain why.
⚠️ Expression tree reconstruction from preorder is a multi-step problem. Know the rule: operators have two children (or one for unary minus), integers are leaves.
⚠️ BST remove() total time is O(h). Be prepared to break it into steps and justify each.
True or false: height() of a BST with n nodes runs in O(h) time. False. It runs in O(n) because every node must be visited.
Fill in the blank: when validating a BST search path, going left from a node with value X means all subsequent values must be less than ____. X (and greater than any lower bound from a previous right turn).
True or false: inorder traversal of an expression tree produces postfix notation. False. Inorder produces infix notation. Postorder produces postfix.
Fill in the blank: BST remove() has overall worst-case time complexity ____. O(h).
Q: A BST contains values 1 to 1000. You search for 363 and visit nodes 925, 202, 911, 240, 912. Is this a valid search path?
A: No. After visiting 911 (going left from it, since 363 < 911), all subsequent values must be < 911. The value 912 violates this bound.
Q: What is the runtime of computing the height of a tree with n nodes?
A: O(n). The recursive height function visits every node exactly once, performing O(1) work at each.
Q: Given preorder traversal × + 8 + 6 3 × 9 + 2 − 3, what is the inorder traversal?
A: 8 + 6 + 3 × 9 × 2 + − 3.
Q: What are the steps and time complexity of remove(key) on a BST of height h?
A: Step 1: find(key) in O(h). Step 2: determine child count in O(1). Step 3: if 0 or 1 child, delete in O(1); if 2 children, find IOP/IOS in O(h), swap in O(1), delete in O(1). Total: O(h).
Q: Why does search sequence validation require tracking both an upper and lower bound?
A: Each left turn establishes a new upper bound (everything below must be smaller), and each right turn establishes a new lower bound (everything below must be larger). Both accumulate as you descend, and a violation of either bound makes the sequence invalid.
Expression trees connect to the broader topic of tree-based parsing in compilers and interpreters. The same reconstruction logic used here appears in syntax tree construction during compilation.
The O(n) runtime of height() is a template for all "visit every node" tree algorithms, including size(), mirror(), and isBalanced(). Any function that must inspect the entire tree is O(n), regardless of the tree's height.
Search sequence validation connects to the concept of BST verification (checking whether a given tree is a valid BST), which uses the same upper/lower bound tracking applied to every node rather than a search path.
Related Terms / Search Tags BST search path, valid search sequence, BST bounds checking, expression tree, infix notation, prefix notation, postfix notation, preorder to inorder, BST remove time complexity, height function runtime, O(h) vs O(n), tree traversal complexity, UIUC data structures exam 2