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

Question

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!

while (predecessor != null && predecessor.right != null) { predecessor = predecessor.right; } Why are you doing this? If you do this it is not O(n). — SomeDude
Does this have any alternative solution without storing elements in array? — NewDev

hyz hyz · Accepted Answer · 2020-05-17T14:39:56

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:

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

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

1 Answers