Tree material is easy to memorize badly. You can recite preorder, inorder, and postorder without understanding what information each order preserves. The course uses binary-tree traversal and BST operations to force a more careful reading of structure.
Binary tree terminology
Definition
Binary tree
A binary tree is a tree in which each node has at most two children, designated as left child and right child when they exist.
The left-right distinction is structural. Two trees can have the same node set and the same parent-child edges but still differ if left and right children are swapped.
Traversal orders
For a binary tree with root , left subtree , and right subtree :
- preorder visits , then , then ;
- inorder visits , then , then ;
- postorder visits , then , then .
These are not three arbitrary lists. They encode different kinds of information.
Worked example
Why inorder alone is not enough
The sequence (B, A, C) can come from different trees. For example, may be
the root with on the left and on the right, but other shapes can also
produce the same inorder list. Inorder alone records left-root-right order, not
the root hierarchy.
Reconstruction needs two compatible traversals
The tutorial emphasizes the standard reconstruction method:
- use preorder or postorder to identify the root;
- use inorder to split the nodes into left and right subtrees;
- repeat recursively on the two subtrees.
Preorder plus inorder is enough when keys are distinct. Postorder plus inorder works similarly. Preorder plus postorder alone usually does not determine a unique binary tree.
Binary search trees
Definition
Binary search tree
A binary search tree is a binary tree with unique keys such that, at every node, all keys in the left subtree are smaller than the node key and all keys in the right subtree are larger than the node key.
The BST invariant is local at every node, but its consequence is global. If a
node has key x, every key deep inside its left subtree must still be less than
x, not merely less than its immediate parent.
Theorem
Inorder traversal of a BST is sorted
If a binary tree satisfies the BST invariant, then an inorder traversal visits the keys in increasing order.
This theorem is why BST questions often ask for inorder successors and ranked traversals.
Inorder successor
The inorder successor of a node is the next node visited by inorder traversal. The tutorial identifies two cases:
- if the node has a right subtree, the successor is the minimum node in that right subtree;
- otherwise, move upward until you find the lowest ancestor for which the current node lies in the ancestor's left subtree.
The second case requires parent information or an equivalent way to retrace the search path from the root.
Worked example
Why the right-subtree case works
If a node has a right subtree, every key there is larger than the node. The smallest key in that right subtree is therefore the next larger key, so it is the inorder successor.
Deletion and replacement
BST deletion has three cases:
- deleting a leaf removes it directly;
- deleting a node with one child connects the parent to that child;
- deleting a node with two children replaces the key with either the maximum of the left subtree or the minimum of the right subtree, then deletes that replacement from its old position.
Both replacement strategies preserve the BST invariant when implemented carefully.
Quick check
Why is inorder traversal of a BST useful?
State the order of visited keys.
Solution
Answer
Quick check
If a BST node has a right subtree, where is its inorder successor?
Use the smaller larger-key idea.
Solution
Answer
Exercises
- Explain why preorder plus inorder can reconstruct a binary tree with distinct keys.
- Give the two cases for finding an inorder successor.
- Explain why replacing a two-child deleted node by the right-subtree minimum preserves the BST invariant.
Solution