How to find x coordinate in a tree?-CodePudding

So i have a program and need to get the location of a node in the form of coordinates x and y , depending on it's location in a tree, meaning that the x coordinate 0 belongs to the left most Node in the entire tree. For example for a tree like this :

the coordinates should be :

node	x	y
5	0	0
2	4	1
1	3	2
4	2	3
3	1	4

while my code gets me:

node	x	y
5	0	0
2	3	1
1	2	2
4	1	3
3	0	4

My code :

static class Node {
        
        Integer value;
        Node leftNode;
        Node rightNode;
        Integer x;
        Integer y;

        Node ( Integer value, Node left, Node right) {
 
            this.value = value;
            leftNode = left;
            rightNode = right;
            this.x = 0;
            this.y = 0;

        }
}

public static void setCoordinates (Node node, int level, int upperX){
            if (node == null) {
                return;
            }
            else {
                node.y = level;
                node.x = xCordinate(node.leftNode, upperX) ;
                
                System.out.println("x :: "   node.x   " y ::  "   node.y   "  node   ::"   node.value);

                setCoordinates(node.leftNode, level   1, 0);
                setCoordinates(node.rightNode, level  1 , node.x);
            }
        }
public static void setCoordinates (Node root) {
   // root is a variable defined in main w
            Node n = root;
            int lvl = 0;
            setCoordinates(n, lvl, 0); 
        }

public static int xCordinate (Node n , Integer upperX) {
            if (n == null){
                return 0;
            }
            else {
                int nrOfLeft =  xCordinate(n.leftNode,0);
                int nrOfRight = xCordinate(n.rightNode,0);
                return nrOfLeft   nrOfRight   1   upperX;
            }
        }

can somebody help me get the correct x coordinate ? The y coordinate isn't giving me any trouble. Thank you for your help !!

CodePudding user response：

public static int setCoordinates (Node node, int level, int nextX){
            if (node == null) {
                return;
            }
            else {
                nextX = setCoordinates(node.leftNode, level   1, nextX);
                node.y = level;
                node.x = nextX;
                
                System.out.println("x :: "   node.x   " y ::  "   node.y   "  node   ::"   node.value);


                nextX = setCoordinates(node.rightNode, level  1 , node.x   1);
                return nextX;
            }
        }

You need to keep track of how many nodes are to the left. There might be some from another left branch on an ancestor.

However if you do an in-order traversal you will visit the nodes in the correct order.

CodePudding user response：

There are three issues:

In the first call of setCoordinates, you should not pass 0 as last argument, as the returned value should be at least upperX. Change to:
```
setCoordinates(node.leftNode, level   1, upperX);
```
In the second call of setCoordinates, you should not pass node.x, as that value is already consumed. You need to pass the minimum value that can be attributed, which is one more:
```
setCoordinates(node.rightNode, level   1, node.x   1); // <--
```
In xCordinate you should never return a value less than upperX, so when the node is null don't return 0, but:
```
if (n == null){
    return upperX;
}
```

With these changes it will work. However, this is inefficient, as you perform a subtree traversal from every node with xCordinate, so this will visit the same node potentially many times. You should revise your algorithm so it can do the job in one sweep. For this you need an in-order traversal.