Kth Ancestor of node in a Binary tree

The problem, simply

You get a binary tree with different values, a target value, and a number k. The 1st ancestor of a node is its parent, the 2nd is its grandparent, and so on. Give back the value of the target's k-th ancestor, or -1 if the target does not have that many ancestors.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write down every person's parent first. Then start at the target and step to the parent k times.

1. Walk the tree with a waiting line (a queue), and for each child store parent[child] = node. Remember the target node when you pass it.
2. Starting from the target, step to its parent k times.
3. If you fall off the top before k steps, answer -1.

import java.util.*;

class Solution {
    public int kthAncestor(TreeNode root, int k, int target) {
        if (root == null) return -1;
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Queue<TreeNode> line = new ArrayDeque<>();
        line.add(root);
        TreeNode start = null;
        while (!line.isEmpty()) {
            TreeNode node = line.poll();
            if (node.val == target) start = node;
            if (node.left != null) { parent.put(node.left, node); line.add(node.left); }
            if (node.right != null) { parent.put(node.right, node); line.add(node.right); }
        }
        TreeNode cur = start;
        for (int step = 0; step < k && cur != null; step++) {
            cur = parent.get(cur);                // one step up; the root has no parent
        }
        return cur == null ? -1 : cur.val;
    }
}

How long it takes: one walk to fill the book, then k steps, O(n). Extra room: a parent entry for every node, O(n). The book is worth it if you will ask many questions on the same tree.

Way 2: the clever way

Search for the target with recursion. When a node hears "found it" from one of its sides, it is one step above the target, so it takes 1 off k. The node where k reaches 0 is the answer. No book, no list.

1. If the node is empty, return "not found".
2. If the node is the target, return "found".
3. Ask the left side; if it says no, ask the right side.
4. If either side said "found": subtract 1 from k. If k is now 0, this node is the answer. Return "found".
5. Otherwise return "not found".

class Solution {
    private int k;
    private int answer;

    public int kthAncestor(TreeNode root, int k, int target) {
        this.k = k;
        this.answer = -1;               // stays -1 if k never reaches 0
        find(root, target);
        return answer;
    }

    // true when the target is somewhere under this node (or is this node)
    private boolean find(TreeNode node, int target) {
        if (node == null) return false;
        if (node.val == target) return true;
        if (find(node.left, target) || find(node.right, target)) {
            k--;                        // I am one more step above the target
            if (k == 0) answer = node.val;
            return true;
        }
        return false;
    }
}

How long it takes: in the worst case we search the whole tree, O(n). Extra room: only the call stack, O(h).

Watch out for

• When k is bigger than the depth, k never reaches 0. Make sure the answer starts as -1.
• || stops early: once the left side finds the target, the right side is never searched. That is good, not a bug.
• The target might not be in the tree. Both ways return -1 then, because no one ever hears "found".

What interviewers ask next

• Answer many queries fast. Use binary lifting: store each node's 1st, 2nd, 4th, 8th ancestor and so on. Then jump using the bits of k, for example k = 5 is a jump of 4 and a jump of 1. Building takes O(n log n), each query O(log n).
• Do it without recursion. Use Way 1, or an iterative walk that keeps the current path in a list, then read path.get(path.size() - 1 - k).
• Find the lowest common ancestor. The same "report up" idea, but now news arrives from two places.
• Nodes have parent pointers already. Then step up k times: O(k) time and O(1) room.

Remember this

Grown-up words: grandparents are ancestors, the parent book is a hash map from child to parent, shouting back up is returning from recursion, and jumping 1, 2, 4, 8 steps at once is binary lifting.