Find depth difference between two nodes in a tree without going all the way up to the root

Question

I Came across a question I couldn't figure out.

Assume A binary tree, where each node has a pointer to its parent, and two children. We receive input for r, p,q ( root, and two nodes from the tree) and we want to find the depth difference between p and q, Without Traversing all the way up to the root.

Limitations and Assumptions:

• No memory usage (meaning no arrays, variables are ok)
• Assume the nodes Lowest Common Ancestor isn't the root (and for simplicity let's assume the LCA is far from the root in Big-O notation Terms.

Just to clarify - Basically, the question is how do we figure out the depth difference without going all the way up to the root, and without memory.

Thanks!

Answer 1

Basically, the question is how do we figure out the depth difference without going all the way up to the root...

It isn't saying that you cannot traverse all the way up to the root. It just says that the final outcome may not be the root.

First, define a function to determine the depth of a node (pseudo code):

function depthOf(r, p):
    depth = 0
    temp = p
    while curr is not r:
        depth++
        temp = temp.parent
    return depth

Simply call this function for both nodes, and take the difference.

As an additional feature, you can use this information to find the Lowest Common Ancestor:

Use the depth difference to walk up from the deepest node of the two up until you are at the same depth as the other. From then on walk upwards from both nodes in tandem, until you arrive at the same node from both sides:

function least(r, p, q)
    diff = depthOf(r, p) - depthOf(r, q)  # The answer
    # In order to find least common ancestor, continue as follows:
    while diff > 0:  # p is deeper than q
        p = p.parent
        diff--
    while diff < 0:  # q is deeper than p
        q = q.parent
        diff++
    while p is not q:
        p = p.parent
        q = q.parent
    return p