0

-- The following lowestCommonAncestor function finds the Lowest Common Ancestor of two nodes, p and q, in a Binary Tree (assuming both nodes exist and all node values are unique).

class Solution {
public:

    bool inBranch(TreeNode* root, TreeNode* node)
    {
        if (root == NULL)
            return false;

        if (root->val == node->val)
            return true;

        return (inBranch(root->left, node) || inBranch (root->right, node));
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        if (root == NULL)
            return NULL;

        if (root->val == p->val || root->val == q->val)
            return root;

        bool pInLeftBranch = false;
        bool qInLeftBranch = false;

        pInLeftBranch = inBranch (root->left, p);
        qInLeftBranch = inBranch (root->left, q);

        //Both nodes are on the left
        if (pInLeftBranch && qInLeftBranch)
            return lowestCommonAncestor(root->left, p, q);
        //Both nodes are on the right
        else if (!pInLeftBranch && !qInLeftBranch)
            return lowestCommonAncestor(root->right, p, q);
        else 
            return root;

    }
};
3
  • "What is the running time complexity of this algorithm?" More that it could be. you traverse several time the same branch to know where are p and q.
    – Jarod42
    Commented Jul 12, 2018 at 14:05
  • this one is O (sqrt (N)), i.e. naive (brute force) algorithm. Bender M., Farach-Colton M. works in O(log(N)) Commented Jul 12, 2018 at 14:21
  • BTW, about run-time complexity and LCA Commented Jul 12, 2018 at 14:24

2 Answers 2

2

Every time you call inBranch(root, node), you are adding O(# of descendents of root) (See time complexity of Binary Tree Search). I will assume the binary tree is balanced for the first calculation of time complexity, then look at the worst case scenario that the tree is unbalanced.

Scenario 1: Balanced Tree

The number of descendants of a node will be roughly half that of its parent. Therefore, each time we recurse, the calls to inBranch will be half as expensive. Let's say N is the total number of nodes in the tree. In the first call to lowestCommonAncestor, we search all N nodes. In subsequent calls we search the left or right half and so on.

O(N + N/2 + N/4 ...) is still the same as O(N).

Scenario 2: Unbalanced Tree

Say this tree is very unbalanced in such a way that all children are on the left side:

     A
    /
   B
  /
 C
/
etc...

The number of descendants decreases by only 1 for each level of recursion. Therefore, our time complexity looks something like:

O(N + (N-1) + (N-2) + ... + 2 + 1) which is equivalent to O(N^2).

Is there a better way?

If this is a Binary Search Tree, we can do as well as O(path_length(p) + path_length(q)). If not, you will always need to traverse the entire tree at least once: O(N) to find the paths to each node, but you can still improve your worst case scenario. I'll leave it to you to figure out the actual algorithm!

1
  • Another case where you can improve things to the sum of path lengths is when each node has a link to its parent. I know that's not always the case, but probably worth it if finding ancestors is a common task. ;)
    – JaMiT
    Commented Jul 12, 2018 at 15:38
1

In the worst case the binary tree is a list of length N where each node has at most one child while p and q are the same leaf node. In that case you will have a running time of O(N^2): You call inBranch (runtime O(N)) on each node on the way down the tree.

If the binary tree is balanced, this becomes O(N log(N)) with N nodes as you can fit O(2^K) nodes into a tree of depth K (and recurse at most K times): Finding each node is O(N), but you only do it a maximum of log(N) times. Check Ben Jones' answer!

Note that a much better algorithm would locate each node once and store a list of the paths down the tree, then compare the paths. Finding each node in the tree (if it is unsorted) is necessarily worst case O(N), the list comparison is also O(N) (unbalanced case) or O(log(N)) (balanced case) so total running time is O(N). You could do even better on a sorted tree, but that's apparently not a given here.

1
  • If the tree is balanced, the algorithm will actually be O(N) because each child node will have roughly half the descendants of its parent. (See my answer below for details.)
    – Ben Jones
    Commented Jul 12, 2018 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.