CODEWITHSUNDEEP
algorithmdata-structurestreebinary-tree
NewDev
NewDev

Reputation: 61

Replace each node in binary tree with the sum of its inorder predecessor and successor

I'm trying to solve this problem without using an array:

Node replaceWithSum(Node root) {
   if (root == null) {
      return null;
   }

   Queue<Node> q = new LinkedList();
   q.add(root);

   Node predecessor, successor = null;
   while(!q.isEmpty()) {
      Node node = q.peek();
      q.remove();

      predecessor = node.left; //possible predecessor
      successor = node.right; //possible successor

      while (predecessor != null && predecessor.right != null) {
           predecessor = predecessor.right;
      }

      while (successor != null && successor.left != null) {
           successor = successor.left;
      }

      node.data = ((predecessor != null)? predecessor.data : 0) + ((successor != null)? 
                                                                   successor.data : 0)


      if (node.left != null) {
         q.add(node.left)
      } 
      if (node.right != null) {
         q.add(node.right)
      }
   }

   return root;
}

Using queue to traverse in level order. I understand space complexity is O(n). Could you please help me understand time complexity of this problem? If tree is skewed, worst case would be possible when we find predecessor/successor only for one node. So worst case for this problem, is when tree is balanced, so is time complexity O(nlogn)?

Thanks in advance!

Upvotes: 0

Views: 371

Answers (1)

hyz
hyz

Reputation: 492

The time complexity is O(n). It's kind of like building a heap.

Suppose you have a full binary tree with height h.

You travel from the root to the leaves, suppose k is the level, it goes from 0 to h-1.

At level k, you have 2^k nodes. For each node, it at most needs to visit h-k node to find its predecessor and successor.

By wolframalpha, we could get this formula:

enter image description here

Obviously, it's equal to O(n).

Upvotes: 1

Related Questions