CODEWITHSUNDEEP
algorithmbinary-tree
Aswin Prasad
Aswin Prasad

Reputation: 417

how to find the position of right most node in last level of complete binary tree?

I am doing a problem in binary trees, and when I came across a problem find the right most node in the last level of a complete binary tree and the issue here is we have to do it in O(n) time which was a stopping point, Doing it in O(n) is simple by traversing all the elements, but is there a way to do this in any complexity less than O(n), I have browsed through internet a lot, and I couldn't get anything regarding the thing. Thanks in advance.

Upvotes: 3

Views: 4011

Answers (5)

Shaggy31
Shaggy31

Reputation: 35

The idea is that for each node compare the height of the left and right subtree. In this way you eliminate half of the nodes in every step. Complexity is O(log n*log n), as you need log n steps to walk down the tree, while getting the height of the subtree takes another log n.

Upvotes: 0

Apoorva Jain
Apoorva Jain

Reputation: 475

This is the recursive solution with time complexity O(lg n* lg n) and O(lg n) space complexity (considering stack storage space).
Space complexity can be reduced to O(1) using Iterative version of the below code.

    // helper function
    int getLeftHeight(TreeNode * node) {
      int c = 0;
      while (node) {
        c++;
        node = node -> left;
      }
      return c;
    }
    
    int getRightMostElement(TreeNode * node) {
      int h = getLeftHeight(node);

      // base case will reach when RightMostElement which is our ans is found
      if (h == 1)
        return node -> val;

      // ans lies in rightsubtree
      else if ((h - 1) == getLeftHeight(node -> right))
        return getRightMostElement(node -> right);

      // ans lies in left subtree
      else getRightMostElement(node -> left);
    }

Time Complexity derivation - At each recursion step, we are considering either left subtree or right subtree i.e. n/2 elements for maximum height (lg n) function calls,
calculating height takes lg n time -

T(n) = T(n/2) + c1 lgn
   = T(n/4) + c1 lgn + c2 (lgn - 1)
   = ...
   = T(1) + c [lgn + (lgn-1) + (lgn-2) + ... + 1]
   = O(lgn*lgn)

Upvotes: 1

lrleon
lrleon

Reputation: 2648

I assume that you know the number of nodes. Let n such number.

In a complete binary tree, a level i has twice the number of nodes than the level i - 1.

So, you could iteratively divide n between 2. If there remainder then n is a right child; otherwise, is a left child. You store into a sequence, preferably a stack, whether there is remainder or not.

Some such as:

Stack<char> s;
while (n > 1)
{
  if (n % 2 == 0)
    s.push('L');
  else
    s.push('R');
  n = n/2; // n would int so division is floor
}

When the while finishes, the stack contains the path to the rightmost node.

The number of times that the while is executed is log_2(n).

Upvotes: 3

amit
amit

Reputation: 178511

Yes, you can do it in O(log(n)^2) by doing a variation of binary search.

This can be done by first going to the leftest element1, then to the 2nd leftest element, then to the 4th leftest element, 8th ,... until you find there is no such element. Let's say the last element you found was the ith, and the first you didn't was 2i.

Now you can simply do a binary search over that range.

This is O(log(n/2)) = O(logn) total iterations, and since each iteration is going down the entire tree, it's total of O(log(n)^2) time.

(1) In here and the followings, the "x leftest element" is referring only to the nodes in the deepest level of the tree.

Upvotes: 2

TomerSH
TomerSH

Reputation: 36

Since it's a complete binary tree, going over all the right nodes until you reach the leaves will take O(logN), not O(N). In regular binary tree it takes O(N) because in the worst case all the nodes are lined up to the right, but since it's a complete binary tree, it can't be

Upvotes: 0

Related Questions