Binary Trees Flashcards
Write a program that takes as input the root of a binary tree and checks whether the tree is height-balanced.
Time O(n) Space O(h) h == height of the tree
private static class BalanceStatusWithHeight {
public boolean balanced;
public int height;
public BalanceStatusWithHeight(boolean balanced, int height) {
this.balanced = balanced;
this.height = height;
}
}
public static boolean isBalanced(BinaryTreeNode tree) {
return checkBalanced(tree).balanced;
}
private static BalanceStatusWithHeight
checkBalanced(BinaryTreeNode tree) {
if (tree == null) {
return new BalanceStatusWithHeight(/*balanced=*/true, /*height=*/-1);
}
BalanceStatusWithHeight leftResult = checkBalanced(tree.left);
if (!leftResult.balanced) {
return leftResult;
}
BalanceStatusWithHeight rightResult = checkBalanced(tree.right);
if (!rightResult.balanced) {
return rightResult;
}
boolean isBalanced = Math.abs(leftResult.height - rightResult.height) <= 1;
int height = Math.max(leftResult.height, rightResult.height) + 1;
return new BalanceStatusWithHeight(isBalanced, height);
}
Write a program that checks whether a binary tree is symmetric.
Time: O(n)
Space: O(h)
public static boolean isSymmetric(BinaryTreeNode tree) {
return tree == null || checkSymmetric(tree.left, tree.right); }
private static boolean checkSymmetric(BinaryTreeNode subtree0,
BinaryTreeNode subtree1) {
if (subtree0 == null && subtree1 == null) {
return true;
} else if (subtree0 != null && subtree1 != null) {
return subtree0.data == subtree1.data &&
checkSymmetric(subtree0.left, subtree1.right) &&
checkSymmetric(subtree0.right, subtree1.left);
}
// One subtree is empty, and the other is not.
return false;
}
Design an algorithm for computing the LCA of two nodes in a binary tree in which nodes do not have a parent field.
Time: O(n)
Space: O(h)
private static class Status {
public int numTargetNodes;
public BinaryTreeNode ancestor;
public Status(int numTargetNodes, BinaryTreeNode node) {
this.numTargetNodes = numTargetNodes;
this.ancestor = node;
}
}
public static BinaryTreeNode lca(BinaryTreeNode tree,
BinaryTreeNode node0,
BinaryTreeNode node1) {
return lcaHelper(tree, node0, node1).ancestor; }
// Returns an object consisting of an int and a node. The int field is
// 0, 1, or 2 depending on how many of {node0, node1} are present in
// the tree. If both are present in the tree, when ancestor is
// assigned to a non-null value, it is the LCA.
private static Status lcaHelper(BinaryTreeNode tree,
BinaryTreeNode node0,
BinaryTreeNode node1) {
if (tree == null) {
return new Status(/*numTargetNodes=*/0, /*ancestor=*/null);
}
Status leftResult = lcaHelper(tree.left, node0, node1);
if (leftResult.numTargetNodes == 2) {
// Found both nodes in the left subtree.
return leftResult;
}
Status rightResult = lcaHelper(tree.right, node0, node1);
if (rightResult.numTargetNodes == 2) {
// Found both nodes in the right subtree.
return rightResult;
}
int numTargetNodes = leftResult.numTargetNodes +
rightResult.numTargetNodes + (tree == node0 ? 1 : 0) +
(tree == node1 ? 1 : 0);
return new Status(numTargetNodes, numTargetNodes == 2 ? tree : null);
}
Given two nodes in a binary tree, design an algorithm that computes their LCA. Assume that each node has a parent pointer.
Time: O(h)
Space: O(1)
public static BinaryTree lca(BinaryTree node0,
BinaryTree node1) {
int depth0 = getDepth(node0), depth1 = getDepth(node1);
// Makes node0 as the deeper node in order to simplify the code.
if (depth1 > depth0) {
BinaryTree temp = node0;
node0 = node1;
node1 = temp;
}
// Ascends from the deeper node.
int depthDiff = Math.abs(depth0 - depth1);
while (depthDiff-- > 0) {
node0 = node0.parent;
}
// Now ascends both nodes until we reach the LCA.
while (node0 != node1) {
node0 = node0.parent;
node1 = node1.parent;
}
return node0;
}
private static int getDepth(BinaryTree node) {
int depth = 0;
while (node.parent != null) {
\++depth;
node = node.parent;
}
return depth;
}
Design an algorithm to compute the sum of the binary numbers represented by the root-to-leaf paths.
Time: O(n)
Space: O(h)
public static int sumRootToLeaf(BinaryTreeNode tree) {
return sumRootToLeafHelper(tree, /*partialPathSum=*/0); }
private static int sumRootToLeafHelper(BinaryTreeNode tree,
int partialPathSum) {
if (tree == null) {
return 0;
}
partialPathSum = partialPathSum * 2 + tree.data;
if (tree.left == null && tree.right == null) { // Leaf.
return partialPathSum;
}
// Non-leaf.
return sumRootToLeafHelper(tree.left, partialPathSum) +
sumRootToLeafHelper(tree.right, partialPathSum);
}
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.
Time: O(n)
Space: O(h)
public static boolean hasPathSum(BinaryTreeNode tree,
int remainingWeight) {
if (tree == null) {
return false;
} else if (tree.left == null && tree.right == null) { // Leaf.
return remainingWeight == tree.data;
}
// Non-leaf.
return hasPathSum(tree.left, remainingWeight - tree.data) ||
hasPathSum(tree.right, remainingWeight - tree.data);
}
Write a nonrecursive function which takes as input a bianry tree and performs an inorder traversal of the tree. Each node contains a value. The result should be returned as an array of node values, ordered according to the inorder traversal order.
Time: O(n)
Space: O(h)
private static class NodeAndState {
public BinaryTreeNode node;
public Boolean leftSubtreeTraversed;
public NodeAndState(BinaryTreeNode node,
Boolean leftSubtreeTraversed) {
this.node = node;
this.leftSubtreeTraversed = leftSubtreeTraversed;
}
}
public static List inorderTraversal(BinaryTreeNode tree) {
List result = new ArrayList<>();
Deque inProcess = new ArrayDeque<>();
inProcess.addFirst(new NodeAndState(tree, /*leftSubtreeTraversed=*/false));
while (!inProcess.isEmpty()) {
NodeAndState nodeAndState = inProcess.removeFirst();
if (nodeAndState.node != null) {
if (nodeAndState.leftSubtreeTraversed) {
result.add(nodeAndState.node.data);
} else {
inProcess.addFirst(new NodeAndState(nodeAndState.node.right,
/*leftSubtreeTraversed=*/false));
inProcess.addFirst(new NodeAndState(nodeAndState.node,
/*leftSubtreeTraversed=*/true));
inProcess.addFirst(new NodeAndState(nodeAndState.node.left,
/*leftSubtreeTraversed=*/false));
}
}
}
return result;
}
Write a program that efficiently computes the kth node appearing in an inorder traversal. Assume that each node stores the number of nodes in the subtree rooted at that node.
Time O(h)
public static BinaryTreeNode
findKthNodeBinaryTree(BinaryTreeNode tree, int k) {
BinaryTreeNode iter = tree;
while (iter != null) {
int leftSize = iter.left != null ? iter.left.size : 0;
if (leftSize + 1 < k) { // k-th node must be in right subtree of iter.
k -= (leftSize + 1);
iter = iter.right;
} else if (leftSize == k - 1) { // k-th is iter itself.
return iter;
} else { // k-th node must be in left subtree of iter.
iter = iter.left;
}
}
// If k is between 1 and the tree size, this line is unreachable.
return null;
}
Design an algorithm that computes the successor of a node in a binary tree. Assume that each node stores its parent.
Time O(h)
public static BinaryTree findSuccessor(BinaryTree node) {
BinaryTree iter = node;
if (iter.right != null) {
// Find the leftmost element in node's right subtree.
iter = iter.right;
while (iter.left != null) {
iter = iter.left;
}
return iter;
}
// Find the closest ancestor whose left subtree contains node.
while (iter.parent != null && iter.parent.right == iter) {
iter = iter.parent;
}
// A return value of null means node does not have successor, i.e., it is
// the rightmost node in the tree.
return iter.parent;
}
Write a nonrecursive program for computing the inorder traversal sequence for a binary tree. Assume nodes have parent fields.
Time O(n) Space O(1)
public static List inorderTraversal(BinaryTree tree) {
BinaryTree prev = null, curr = tree;
List result = new ArrayList<>();
while (curr != null) {
BinaryTree next;
if (curr.parent == prev) {
// We came down to curr from prev.
if (curr.left != null) { // Keep going left.
next = curr.left;
} else {
result.add(curr.data);
// Done with left, so go right if right is not empty.
// Otherwise, go up.
next = (curr.right != null) ? curr.right : curr.parent;
}
} else if (curr.left == prev) {
result.add(curr.data);
// Done with left, so go right if right is not empty. Otherwise, go up.
next = (curr.right != null) ? curr.right : curr.parent;
} else { // Done with both children, so move up.
next = curr.parent;
}
prev = curr;
curr = next;
}
return result;
}
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. Time O(n) Space O(n + h)
public static BinaryTreeNode
binaryTreeFromPreorderInorder(List preorder, List inorder) {
return binaryTreeFromPreorderInorderHelper(
preorder, /*preorderStart=*/0, preorder.size(), /*inorderStart=*/0,
inorder.size(),
IntStream.range(0, inorder.size())
.boxed()
.collect(Collectors.toMap(i -> inorder.get(i), i -> i))); }
// Builds the subtree with preorder.subList(preorderStart, preorderEnd) and
// inorder.subList(inorderStart, inorderEnd).
private static BinaryTreeNode
binaryTreeFromPreorderInorderHelper(List preorder, int preorderStart,
int preorderEnd, int inorderStart,
int inorderEnd,
Map nodeToInorderIdx) {
if (preorderEnd <= preorderStart || inorderEnd <= inorderStart) {
return null;
}
int rootInorderIdx = nodeToInorderIdx.get(preorder.get(preorderStart));
int leftSubtreeSize = rootInorderIdx - inorderStart;
return new BinaryTreeNode<>(
preorder.get(preorderStart),
// Recursively builds the left subtree.
binaryTreeFromPreorderInorderHelper(
preorder, preorderStart + 1, preorderStart + 1 + leftSubtreeSize,
inorderStart, rootInorderIdx, nodeToInorderIdx),
// Recursively builds the right subtree.
binaryTreeFromPreorderInorderHelper(
preorder, preorderStart + 1 + leftSubtreeSize, preorderEnd,
rootInorderIdx + 1, inorderEnd, nodeToInorderIdx)); }
Design an algorithm for reconstructing a binary tree from a preorder traversal visit sequence that uses null to mark empty children.
Time O(n)
private static Integer subtreeIdx;
public static BinaryTreeNode
reconstructPreorder(List preorder) {
subtreeIdx = 0;
return reconstructPreorderSubtree(preorder);
}
// Reconstructs the subtree that is rooted at subtreeIdx.
private static BinaryTreeNode
reconstructPreorderSubtree(List preorder) {
Integer subtreeKey = preorder.get(subtreeIdx);
\++subtreeIdx;
if (subtreeKey == null) {
return null;
}
// Note that reconstructPreorderSubtree updates subtreeIdx. So the order of
// following two calls are critical.
BinaryTreeNode leftSubtree = reconstructPreorderSubtree(preorder);
BinaryTreeNode rightSubtree = reconstructPreorderSubtree(preorder);
return new BinaryTreeNode<>(subtreeKey, leftSubtree, rightSubtree);
}
Given a binary tree, return the leaves of the binary tree. The leaves should appear in left-to-right order. Time O(n) Space O(n)
public static List>
createListOfLeaves(BinaryTreeNode tree) {
List> leaves = new ArrayList<>(); addLeavesLeftToRight(tree, leaves); return leaves; }
private static void
addLeavesLeftToRight(BinaryTreeNode tree,
List> leaves) {
if (tree != null) {
if (tree.left == null && tree.right == null) {
leaves.add(tree);
} else {
addLeavesLeftToRight(tree.left, leaves);
addLeavesLeftToRight(tree.right, leaves);
}
}
}
Write a program that computes the exterior of a binary tree.
Time O(n)
public static List>
exteriorBinaryTree(BinaryTreeNode tree) {
if (tree == null) {
return Collections.emptyList();
}
List> exterior = new ArrayList<>() {
{ add(tree); }
};
leftBoundary(tree.left, exterior);
leaves(tree.left, exterior);
leaves(tree.right, exterior);
rightBoundary(tree.right, exterior);
return exterior;
}
// Computes the nodes from the root to the leftmost leaf.
private static void leftBoundary(BinaryTreeNode subtree,
List> exterior) {
if (subtree == null || (subtree.left == null && subtree.right == null)) {
return;
}
exterior.add(subtree);
if (subtree.left != null) {
leftBoundary(subtree.left, exterior);
} else {
leftBoundary(subtree.right, exterior);
}
}
// Computes the nodes from the rightmost leaf to the root.
private static void rightBoundary(BinaryTreeNode subtree,
List> exterior) {
if (subtree == null || (subtree.left == null && subtree.right == null)) {
return;
}
if (subtree.right != null) {
rightBoundary(subtree.right, exterior);
} else {
rightBoundary(subtree.left, exterior);
}
exterior.add(subtree);
}
// Compute the leaves in left-to-right order.
private static void leaves(BinaryTreeNode subtree,
List> exterior) {
if (subtree == null) {
return;
}
if (subtree.left == null && subtree.right == null) {
exterior.add(subtree);
return;
}
leaves(subtree.left, exterior);
leaves(subtree.right, exterior);
}
Write a program that takes a perfect binary tree, and sets each node’s level-next field to the nodes on the right, if one exists.
Time O(n) Space O(1)
public static void constructRightSibling(BinaryTreeNode tree) {
while (tree != null) {
populateLowerLevelNextField(tree);
tree = tree.left;
}
}
private static void
populateLowerLevelNextField(BinaryTreeNode startNode) {
while (startNode != null && startNode.left != null) {
// Populate left child's next field.
startNode.left.next = startNode.right;
// Populate right child's next field if startNode is not the last node
// of this level.
if (startNode.next != null) {
startNode.right.next = startNode.next.left;
}
startNode = startNode.next;
}
}
