Binary Trees

Problems

10.1

A binary tree is said to be height-balanced if for each node in the tree, the difference in the height of its left and right subtrees is at most one. A perfect binary tree is height-balanced, as is a complete binary tree. A height-balanced binary tree does not have to be perfect or complete.

Write a program that takes as input the root of a binary tree and checks whether the tree is height-balanced.

Hint: Think of a classic binary tree algorithm.

Variant: Write a program that returns the size of the largest subtree that is complete.

Variant: Define a node in a binary tree to be $k$ -balanced if the difference in the number of nodes in its left and right subtrees is no more than $k$ . Design an algorithm that takes as input a binary tree and positive integer $k$ , and returns a node in the binary tree such that the node is not $k$ -balanced, but all of its descendants are $k$ -balanced. For example, when applied to the binary tree in Figure 10.1 on Page 148, if $k = 3$ , your algorithm should return Node $J$ .

10.2

A binary tree is symmetric if you can draw a vertical line through the root and then the left subtree is the mirror image of the right subtree.

Write a program that checks whether a binary tree is symmetric.

Hint: The definition of symmetry is recursive.

10.3

Any two nodes in a binary tree have a common ancestor, namely the root. The lowest common ancestor (LCA) of any two nodes in a binary tree is the node furthest from the root that is an ancestor of both nodes. For example, the LCA of $M$ and $N$ in Figure 10.1 on Page 148 is $K$ .

Design an algorithm for computing the LCA of two nodes in a binary tree in which nodes do not have a parent field.

Hint: When is the root the LCA?

10.4

Given two nodes in a binary tree, design an algorithm that computes their LCA. Assume that each node has a parent pointer.

Hint: The problem is easy if both nodes are the same distance from the root.

10.5

Consider a binary tree in which each node contains a binary digit. A root-to-leaf path can be associated with a binary number, with the MSB at the root. As an example, the binary tree in Figure 10.4 represents the numbers $(1000)_{2}$ , $(1001)_{2}$ , $(10110)_{2}$ , $(110011)_{2}$ , $(11000)_{2}$ , and $(1100)_{2}$ .

Design an algorithm to compute the sum of the binary numbers represented by the root-to-leaf paths.

Hint: Think of an appropriate way of traversing the tree.

10.6

You are given a binary tree where each node is labeled with an integer. The path weight of a node in such a tree is the sum of the integers on the unique path from the root to that node. For the example shown in Figure 10.1 on Page 148, the path weight of $E$ is 591.

Write a program which takes as input an integer and a binary tree with integer node weights, and checks if there exists a leaf whose path weight equals the given integer.

Hint: What do you need to know about the rest of the tree when checking a specific subtree?

Variant: Write a program which takes the same inputs as in Problem 10.6 and returns all the paths to leaves whose weight equals $s$ . For example, if $s = 619$ , you should return $⟨⟨ A, B, C, D ⟩, ⟨ A, I, O, P ⟩⟩$ .

10.7

This problem is concerned with traversing nodes in a binary tree in inorder fashion. See Page 149 for details and examples of these traversals. Generally speaking, a traversal computation is easy to implement if recursion is allowed.

Write a program which takes as input a binary tree and performs an inorder traversal of the tree. Do not use recursion. Nodes do not contain parent references.

Hint: Simulate the function call stack.

10.8

This problem is concerned with traversing nodes in a binary tree in preorder fashion. See Page 149 for details and examples of these traversals. Generally speaking, a traversal computation is easy to implement if recursion is allowed.

Write a program which takes as input a binary tree and performs a preorder traversal of the tree. Do not use recursion. Nodes do not contain parent references.

10.9

It is trivial to find the $k$ th node that appears in an inorder traversal with $O (n)$ time complexity, where $n$ is the number of nodes. However, with additional information on each node, you can do better.

Write a program that efficiently computes the $k$ th node appearing in an inorder traversal. Assume that each node stores the number of nodes in the subtree rooted at that node.

Hint: Use the divide and conquer principle.

10.10

The successor of a node in a binary tree is the node that appears immediately after the given node in an inorder traversal. For example, in Figure 10.1 on Page 148, the successor of $G$ is $A$ , and the successor of $A$ is $J$ .

Design an algorithm that computes the successor of a node in a binary tree. Assume that each node stores its parent.

Hint: Study the node’s right subtree. What if the node does not have a right subtree?

10.11

The direct implementation of an inorder traversal using recursion has $O (h)$ space complexity, where $h$ is the height of the tree. Recursion can be removed with an explicit stack, but the space complexity remains $O (h)$ .

Write a nonrecursive program for computing the inorder traversal sequence for a binary tree. Assume nodes have parent fields.

Hint: How can you tell whether a node is a left child or right child of its parent?

Variant: How would you perform preorder and postorder traversals iteratively using $O (1)$ additional space? Your algorithm cannot modify the tree. Nodes have an explicit parent field.

10.12

Many different binary trees yield the same sequence of keys in an inorder, preorder, or postorder traversal. However, given an inorder traversal and one of any two other traversal orders of a binary tree, there exists a unique binary tree which yields those orders, assuming each node holds a distinct key. For example, the unique binary tree whose inorder traversal sequence is $⟨ F, B, A, E, H, C, D, I, G ⟩$ and whose preorder traversal sequence is $⟨ H, B, F, E, A, C, D, G, I ⟩$ is given in Figure 10.5.

Given an inorder traversal sequence and a preorder traversal sequence of a binary tree, write a program to reconstruct the tree. Assume each node has a unique key.

Hint: Focus on the root.

Variant: Solve the same problem with an inorder traversal sequence and a postorder traversal sequence.

Variant: Let $A$ be an array of $n$ distinct integers. Let the index of the maximum element of $A$ be $m$ . Define the max-tree on $A$ to be the binary tree on the entries of $A$ in which the root contains the maximum element of $A$ , the left child is the max-tree on $A [0 : m - 1]$ and the right child is the max-tree on $A [m + 1 : n - 1]$ . Design an $O (n)$ algorithm for building the max-tree of $A$ .

10.13

Many different binary trees have the same preorder traversal sequence.

In this problem, the preorder traversal computation is modified to mark where a left or right child is empty. For example, the binary tree in Figure 10.5 on Page 163 yields the following preorder traversal sequence:

$⟨ H, B, F, null, null, E, A, null, null, null, C, null, D, null, G, I, null, null, null ⟩$

Design an algorithm for reconstructing a binary tree from a preorder traversal visit sequence that uses null to mark empty children.

Hint: It’s difficult to solve this problem by examining the preorder traversal visit sequence from left-to-right.

Variant: Solve the same problem when the sequence corresponds to a postorder traversal sequence. Is this problem solvable when the sequence corresponds to an inorder traversal sequence?

10.14

In some applications of a binary tree, only the leaf nodes contain actual information. For example, the outcomes of matches in a tennis tournament can be represented by a binary tree where leaves are players. The internal nodes correspond to matches, with a single winner advancing. For such a tree, we can link the leaves to get a list of participants.

Given a binary tree, compute a linked list from the leaves of the binary tree. The leaves should appear in left-to-right order. For example, when applied to the binary tree in Figure 10.1 on Page 148, your function should return $⟨ D, E, H, M, N, P ⟩$ .

Hint: Build the list incrementally. It’s easy if the partial list is a global.

10.15

The exterior of a binary tree is the following sequence of nodes: the nodes from the root to the leftmost leaf, followed by the leaves in left-to-right order, followed by the nodes from the rightmost leaf to the root. By leftmost (rightmost) leaf, we mean the leaf that appears first (last) in an inorder traversal. For example, the exterior of the binary tree in Figure 10.1 on Page 148 is $⟨ A, B, C, D, E, H, M, N, P, O, I ⟩$ .

Write a program that computes the exterior of a binary tree.

Hint: Handle the root’s left child and right child in mirror fashion.

10.16

For this problem, assume that each binary tree node has an extra field, call it level-next, that holds a binary tree node (this field is distinct from the fields for the left and right children). The level-next field will be used to compute a map from nodes to their right siblings. The input is assumed to be a perfect binary tree. See Figure 10.6 for an example.

Write a program that takes a perfect binary tree, and sets each node’s level-next field to the node on its right, if one exists.

Hint: Think of an appropriate traversal order.

Variant: Solve the same problem when there is no level-next field. Your result should be stored in the right child field.

Variant: Solve the same problem for a general binary tree. See Figure 10.7 for an example.

10.17

This problem is concerned with the design of an API for setting the state of nodes in a binary tree to lock or unlock. A node’s state cannot be set to lock if any of its descendants or ancestors are in lock.

Changing a node’s state to lock does not change the state of any other nodes. For example, all leaves may simultaneously be in state lock. (If this is the case, no nonleaf nodes can be in state lock.)

Write the following methods for a binary tree node class:

A function to test if the node is locked.
A function to lock the node. If the node cannot be locked, return false, otherwise lock it and return true.
A function to unlock the node.

Assume that each node has a parent field. The API will be used in a single-threaded program, so there is no need for concurrency constructs such as mutexes or synchronization.

Hint: Track the number of locked nodes for each subtree.

Answers

10.1

Do a postorder traversal that returns two pieces of information for each subtree: whether it is balanced and what its height is. As soon as a child subtree is found unbalanced, propagate failure upward without exploring irrelevant work. At each node, compare the left and right heights and return the larger height plus one. This runs in $O (n)$ time and $O (h)$ space from the call stack.

10.2

Check symmetry by recursing on pairs of mirror-positioned subtrees. Two subtrees are mirrors if their roots have equal keys and the left child of one is a mirror of the right child of the other, and vice versa. The algorithm visits each node once, so it takes $O (n)$ time and $O (h)$ space.

10.3

Use a postorder traversal that returns how many target nodes were found in the current subtree, together with the LCA when both are present. If the left or right subtree already contains both targets, propagate that result immediately. Otherwise add the matches from the two children and the current node; when the total reaches two, the current node is the LCA. This is $O (n)$ time and $O (h)$ space.

10.4

Compute the depth of each node using parent pointers. Advance the deeper node upward until both nodes are at the same depth, then move them upward in tandem until they meet. The meeting point is the LCA. The running time is $O (h)$ and the extra space is $O (1)$ .

10.5

Traverse root to leaf while maintaining the integer encoded by the current path. When descending to a child, update the partial value with partial = 2 * partial + bit. If the current node is a leaf, return that value; otherwise return the sum from the left and right subtrees. Every node is processed once, so the algorithm runs in $O (n)$ time and uses $O (h)$ space.

10.6

Perform a depth-first traversal carrying the root-to-current-node sum. At a leaf, compare the accumulated sum with the target. For an internal node, recurse on its children with the updated sum and short-circuit as soon as one subtree succeeds. This yields $O (n)$ time and $O (h)$ space. For the variant, keep the current path as you recurse and emit each root-to-leaf path whose final sum matches the target.

10.7

Simulate recursion with an explicit stack and a current pointer. Repeatedly walk left, pushing nodes along the way. When you can go no further left, pop the top node, visit it, and continue with its right child. Each node is pushed and popped once, so the traversal takes $O (n)$ time and $O (h)$ space.

10.8

Use a stack initialized with the root. Repeatedly pop a node, visit it, then push its right child followed by its left child so the left subtree is processed first. Aside from null checks, each node is pushed and popped once, giving $O (n)$ time and $O (h)$ space.

10.9

Let $L$ be the size of the current node’s left subtree. If $k = L + 1$ , the current node is the answer. If $k \leq L$ , continue into the left subtree. Otherwise continue into the right subtree with $k - (L + 1)$ . Each step descends one level, so the running time is $O (h)$ and the extra space is $O (1)$ .

10.10

If the node has a right subtree, its successor is the leftmost node in that right subtree. Otherwise, climb parent pointers until you first move up from a left child; that parent is the successor. If no such ancestor exists, the node is the rightmost node in the tree and has no successor. The time complexity is $O (h)$ and the extra space is $O (1)$ .

10.11

With parent pointers, keep prev and curr pointers to record the direction of movement. The next step depends on whether you arrived at curr from its parent, its left child, or its right child. That state is enough to decide whether to go left, visit the current node, go right, or move up. Each edge is traversed a constant number of times, so the traversal runs in $O (n)$ time and $O (1)$ extra space.

10.12

The first key in preorder is the root. Find that root in the inorder sequence; everything to its left belongs to the left subtree and everything to its right belongs to the right subtree. Recurse on the corresponding preorder slices. To avoid repeatedly searching inorder, precompute a hash table from key to inorder index. The result is $O (n)$ time and $O (n)$ space.

10.13

Read the marked preorder sequence with a shared index. At each step, if the current token is null, return an empty subtree. Otherwise create a node from the token, then recursively build its left subtree and right subtree in that order. Because each token is consumed once, the running time is $O (n)$ and the extra space is $O (h)$ for recursion.

10.14

Traverse the tree left to right and append each leaf as soon as it is encountered. Because the traversal order already matches the desired leaf order, no sorting or second pass is needed. The algorithm visits every node once, so it runs in $O (n)$ time and uses $O (h)$ space beyond the output list.

10.15

Construct the exterior as three pieces while avoiding duplicates: the root, the left boundary together with leaves from the left subtree, and the leaves plus reversed right boundary from the right subtree. A clean implementation handles the left and right sides symmetrically with helper routines that know whether the current node lies on the boundary. This is $O (n)$ time and $O (h)$ extra space.

10.16

Exploit the perfect-tree structure level by level. For a node on a populated level, its left child’s right sibling is its right child, and its right child’s right sibling is the left child of the node’s own right sibling. Once one level’s level-next pointers are set, they let you walk that level left to right while wiring the next one. The whole tree is processed in $O (n)$ time and $O (1)$ extra space.

10.17

Store two extra fields per node: a Boolean locked flag and a count of locked descendants. isLocked() simply returns the flag. To lock a node, first reject it if its descendant count is nonzero or if any ancestor is locked; on success, set the flag and increment the locked-descendant count along the ancestor chain. To unlock, clear the flag and decrement those ancestor counts. isLocked() is $O (1)$ , while lock and unlock are both $O (h)$ time with $O (1)$ extra space per operation.

Takashi's Notes

Explorer

Binary Trees

Binary Trees

Problems

10.1

10.2

10.3

10.4

10.5

10.6

10.7

10.8

10.9

10.10

10.11

10.12

10.13

10.14

10.15

10.16

10.17

Answers

10.1

10.2

10.3

10.4

10.5

10.6

10.7

10.8

10.9

10.10

10.11

10.12

10.13

10.14

10.15

10.16

10.17

Graph View

Table of Contents

Backlinks