Assign in-order index to Binary Tree

How do we assign in-order index to binary tree?

Given a tree below:

      1
   2      3
4    5  6   7

Assign an index below to above tree as you can see below:

      4
   2      6
1    3  5    7

Following code does not work for case 6 as it assigns 10 as we are double counting passed down index from the argument and from the left child. Can we achieve this without using global variable?

  int assignIndex(Node root, int index) {
        if (root == null)
            return 0;

        int leftIndex = assignIndex(root.left, index);

        root.index = leftIndex + index + 1;

        int rightIndex = assignIndex(root.right, root.index);

        if (rightIndex == 0)
            return root.index;
        else
            return rightIndex;
    }

1 answer

  • answered 2018-03-07 03:30 Len

    The problem in the above program is return of two different values at two different occasions. So the issue can be solved by returning only latest index values at all occasions if you don't want to use global variables.

    int assignIndex(Node root, int index) {
    
        if (root.left != null)
           index = assignIndex(root.left, index);  
    
        index++;
        root.index = index;
    
        if (root.right != null)
           index = assignIndex(root.right, index);
    
        return index;
    
    }