Find the Lowest Node Above Both Chosen Nodes
Solve this ProblemYou are given the root of a binary tree in which all node values are distinct, and two values p and q that are both present in the tree. Return the value of the lowest node that has both the node holding p and the node holding q somewhere in its subtree. A node is considered to be part of its own subtree, so if one of the two chosen nodes lies below the other, the upper one is the answer.
You can compare the root paths of the two nodes, or use a single recursive pass in which each subtree reports whether it contains a target.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ number of nodes ≤ 100, and every node value is distinct, 1 ≤ node.val ≤ 1000 - ◆
p and q are values that both exist in the tree (they may be equal to each other) - ◆
The tree is given as its root node; each node has a val, a left child and a right child - ◆
Return the value of the lowest node that has both the p-node and the q-node in its subtree. A node counts as being in its own subtree, so if one chosen node is above the other, the answer is the upper one
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Find Both Root Paths, Then Compare Them
GoodEvery node's ancestors are exactly the nodes on its path from the root. So find the path from the root to p and the path from the root to q (a depth-first search that adds a node when entering it and removes it when the target is not below). The two paths start together — both begin at the root — and stay identical until the tree splits them. The last node they share is the lowest shared ancestor. It needs two searches (each up to n nodes) and stores two paths of length up to h: O(n) time, O(h) space.
O(n)O(h)1class Solution {
2 public int lowestSharedAncestor(TreeNode root, int p, int q) {
3 List<Integer> a = new ArrayList<>();
4 List<Integer> b = new ArrayList<>();
5 pathTo(root, p, a);
6 pathTo(root, q, b);
7 int i = 0;
8 while (i < a.size() && i < b.size() && a.get(i).equals(b.get(i))) i++;
9 return a.get(i - 1);
10 }
11
12 private boolean pathTo(TreeNode node, int target, List<Integer> path) {
13 if (node == null) return false;
14 path.add(node.val);
15 if (node.val == target) return true;
16 if (pathTo(node.left, target, path) || pathTo(node.right, target, path)) return true;
17 path.remove(path.size() - 1);
18 return false;
19 }
20}Optimal — One Recursive Pass That Reports Where the Targets Were Found
OptimalLet find(node) answer: "what did I find in this subtree?" It returns the node itself as soon as it is p or q (there is no need to look below it: if the other target is underneath, this node is the answer; if not, this node is what we report up), and null for an empty subtree. For any other node, ask both children. If BOTH report something, one target is in each subtree, so this node is the lowest shared ancestor — return it. If only one side reported, pass that result up unchanged (it is either a single target or an already-found ancestor). Because both values are guaranteed to exist, the root's answer is the ancestor. One pass: O(n) time, O(h) space, no paths stored.
O(n)O(h)1class Solution {
2 public int lowestSharedAncestor(TreeNode root, int p, int q) {
3 return find(root, p, q).val;
4 }
5
6 private TreeNode find(TreeNode node, int p, int q) {
7 if (node == null || node.val == p || node.val == q) return node;
8 TreeNode left = find(node.left, p, q);
9 TreeNode right = find(node.right, p, q);
10 if (left != null && right != null) return node;
11 return left != null ? left : right;
12 }
13}