"Trees & Binary Search Trees" — Practice

Question 1

What is the maximum number of nodes in a binary tree of height 4, with height measured in edges?

Accepted Answer

A

Question 2

Which traversal of a binary search tree produces the keys in sorted order?

Accepted Answer

B

Question 3

A strictly binary tree has 12 internal nodes. How many leaves does it have?

Accepted Answer

C

Question 4

A binary tree has inorder traversal D B E A F C G and preorder traversal A B D E C F G. Give its postorder traversal.

Accepted Answer

The first preorder element is always the root, so A is the root.

Locate A in the inorder: D B E to its left and F C G to its right. Those are the left and right subtrees.

The left subtree has 3 nodes, so the next 3 preorder elements after A describe it: B D E. Its inorder is D B E.

Within the left subtree, B is the root, D is to its left in the inorder and E to its right. Both are leaves.

The right subtree has preorder C F G and inorder F C G. C is the root, F is to its left and G to its right. Both are leaves.

The complete tree has root A, with B on the left holding children D and E, and C on the right holding children F and G.

Postorder visits left subtree, right subtree, then node, applied recursively.

Left subtree postorder: D E B. Right subtree postorder: F G C. Then the root: A.

The postorder traversal is D E B F G C A.

Note that this tree is strictly binary, so preorder plus postorder would also have determined it uniquely. Had any node had a single child, inorder would have been indispensable.

Question 5

Insert 45, 25, 60, 15, 35, 55, 70, 30, 40 into an empty BST. Then delete 25 using the inorder successor. Give the resulting inorder traversal and the tree height.

Accepted Answer

Insertion places each key by descending from the root and turning left or right by comparison.

45 is the root. 25 goes left. 60 goes right. 15 goes left of 25. 35 goes right of 25. 55 goes left of 60. 70 goes right of 60. 30 is less than 45, greater than 25, less than 35, so it becomes 35's left child. 40 follows the same path but is greater than 35, so it becomes 35's right child.

Now delete 25. It has two children, 15 and 35, so the third deletion case applies.

The inorder successor is the leftmost node of the right subtree. Descending from 35 and going left gives 30, which is a leaf.

Copy 30 into the node holding 25, then delete the original 30, which is a leaf and is removed directly.

The tree now has root 45, with left child 30 holding children 15 and 35, where 35 has a single right child 40. The right side is unchanged: 60 with children 55 and 70.

Inorder traversal: 15, 30, 35, 40, 45, 55, 60, 70. Note that it remains sorted, which is the check worth performing after any BST modification.

Height in edges: the longest path is 45 to 30 to 35 to 40, which is 3 edges, so the height is 3.

Question 6

What is the maximum height of an AVL tree containing 12 nodes, with height measured in edges?

Accepted Answer

Work from the minimum-node recurrence, which gives the fewest nodes an AVL tree of a given height can contain. A tree of height h is most economical when its root has minimal subtrees of heights h minus 1 and h minus 2, the most unbalanced arrangement the AVL condition permits.

N(h) = N(h-1) + N(h-2) + 1, with N(0) = 1 and N(1) = 2.

N(2) = 2 + 1 + 1 = 4.
N(3) = 4 + 2 + 1 = 7.
N(4) = 7 + 4 + 1 = 12.
N(5) = 12 + 7 + 1 = 20.

A height of 4 requires at least 12 nodes, which is exactly what we have, so height 4 is achievable.

A height of 5 would require at least 20 nodes, which we do not have, so height 5 is impossible.

The maximum height is therefore 4.

For comparison, the minimum height for 12 nodes is the ceiling of log base 2 of 13, minus 1, which is 4 minus 1 = 3. So a 12-node AVL tree has height 3 or 4, while an unbalanced binary tree could reach height 11.

Question 7

Insert 30, 20, 40, 10, 25, 35, 5, 15 into an empty AVL tree, identifying every rotation performed.

Accepted Answer

Insert 30: root, balanced.

Insert 20: left child of 30. Root balance factor is 1 minus minus-1, that is 1. Permitted.

Insert 40: right child of 30. Root balance factor is 0. Permitted.

Insert 10: left child of 20. Node 20 has balance factor 1; node 30 has left subtree of height 1 and right of height 0, giving 1. Permitted.

Insert 25: right child of 20. Node 20 now has both children, balance factor 0. Node 30 has left height 1, right height 0, balance factor 1. Permitted.

Insert 35: left child of 40. Node 40 has balance factor 1; node 30 has left height 1 and right height 1, balance factor 0. Permitted.

Insert 5: left child of 10. Now trace upward. Node 10 has balance factor 1. Node 20 has left subtree of height 1 and right of height 0, giving 1, still permitted. Node 30 has left subtree of height 2 and right of height 1, giving 1. Permitted throughout, so no rotation.

Insert 15: right child of 10. Node 10 now has children 5 and 15, balance factor 0. Node 20 has left height 1, right height 0, balance factor 1. Node 30 has left height 2, right height 1, balance factor 1. Still permitted, so again no rotation.

No rotation is required for this sequence, which is itself the instructive result: the insertions happened to keep every subtree within one level of balance. A single further insertion of 1 or 3 below node 5 would create a left-left violation at node 20 and force a single right rotation.

Question 8

How many distinct binary search trees can be formed from 5 distinct keys, and how many distinct labelled binary trees exist on 5 nodes? Explain the difference.

Accepted Answer

For binary search trees, the shape alone determines the tree, because the ordering invariant forces each key into exactly one position once a shape is chosen. So the count is the fifth Catalan number.

C_5 = (1/6) times C(10, 5) = (1/6) times 252 = 42.

There are 42 distinct binary search trees on 5 keys.

The recursive derivation confirms it. Choosing the k-th smallest key as the root puts k minus 1 keys on the left and 5 minus k on the right, so the count is the sum over k of C(k-1) times C(5-k).

That is C0 C4 + C1 C3 + C2 C2 + C3 C1 + C4 C0 = 1(14) + 1(5) + 2(2) + 5(1) + 14(1) = 14 + 5 + 4 + 5 + 14 = 42.

For labelled binary trees, the shape can be chosen in 42 ways as before, but the 5 labels may then be assigned to the 5 positions in any order, giving 5 factorial = 120 assignments per shape.

The total is 42 times 120 = 5040.

The difference is exactly the ordering constraint. A BST removes all label freedom, since only one arrangement of the keys satisfies the invariant for a given shape, so the BST count is the pure shape count while the labelled count multiplies by every permutation.

Question 9

Explain why preorder and postorder together cannot reconstruct a general binary tree, giving a concrete pair of trees that share both, and state when the pair does suffice.

Accepted Answer

The ambiguity arises exactly when a node has a single child, because neither traversal records which side that child is on.

Consider a tree with root A and a single child B on the left. Preorder visits A then B, giving A B. Postorder visits B then A, giving B A.

Now consider a tree with root A and a single child B on the right. Preorder visits A then B, giving A B. Postorder visits B then A, giving B A.

The two trees are structurally different — one leans left and the other right — yet they produce identical preorder and identical postorder traversals. No amount of additional reasoning can distinguish them from those two sequences alone.

Inorder resolves it immediately. The left-leaning tree has inorder B A while the right-leaning one has A B, so the two are separated by the position of the root within the sequence.

The general principle is that preorder fixes the root at the front of each segment and postorder fixes it at the back, but neither indicates where the boundary between the left and right subtrees falls. Inorder supplies exactly that boundary, since the root's position in the inorder splits the remaining keys into the two subtrees.

The pair does suffice for a strictly binary tree, where every node has either 0 or 2 children. The single-child case cannot arise, so the second element of the preorder is unambiguously the root of the left subtree and the boundary can be located by matching it against the postorder.

Practice — "Trees & Binary Search Trees"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities