The height of a tree is the length of the longest path from the root to a leaf. What is the maximum number of nodes in a binary tree of height h (where height of a single node tree is 0)?
For height h (with root at height 0), the maximum number of nodes occurs in a perfect binary tree, which is $2^0 + 2^1$ + ... + 2^$h = 2^{h+1} - 1$.
Postorder traversal of a given binary search tree T produces: 10, 20, 15, 30, 25. Which of the following is the preorder traversal of T?
In a BST, Inorder is always sorted: 10, 15, 20, 25, 30. Given Postorder: 10, 20, 15, 30, 25. Root is 25. Left subtree contains {10, 15, 20} (root 15), Right subtree contains {30}. Preorder = Root, Left, Right = 25, 15, 10, 20, 30.
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 40, 35, 50. Which of the following is the postorder traversal sequence?
Preorder: 30, 20, 10, 15, 25, 40, 35, 50. Root is 30. Left BST elements < 30: {20, 10, 15, 25}. Right BST elements > 30: {40, 35, 50}. Postorder = Left(15, 10, 25, 20) + Right(35, 50, 40) + Root(30) = 15, 10, 25, 20, 35, 50, 40, 30.
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty Binary Search Tree. What is the height of the binary search tree (where height is the number of edges on the longest path from root to leaf)?
Insert 7 (lvl 0). 5 (<7, lvl 1), 1 (<5, lvl 2), 8 (>7, lvl 1), 3 (>1, lvl 3), 6 (>5, lvl 2), 0 (<1, lvl 3), 9 (>8, lvl 2), 4 (>3, lvl 4), 2 (<3, lvl 4). Maximum depth is at node 4 and node 2 at level 4. Height = 4 edges.
For a full binary tree (every node has either 0 or 2 children), which additional traversal, when paired with a given preorder traversal, is sufficient to uniquely reconstruct the tree?
For a full binary tree, preorder together with postorder uniquely determines the tree structure (under the standard definition of a full binary tree).