# Change node values to their heights in a binary tree

My task is to change the values of nodes to their heights in a binary tree. By the condition of the task, you need to change all the values in 1 pass of the tree, but you can violate this condition using additional data structures. I have a code, but it does not work correctly. This is the original tree, here is what I want to get, and this is the result of the program written below

```public void replaceValuesToHeight() {
ArrayDeque<TreeNode> leftTreeQueue = new ArrayDeque<>();
ArrayDeque<TreeNode> rightTreeQueue = new ArrayDeque<>();
replaceValuesToHeight(getRoot(), new ArrayDeque<>(), new ArrayDeque<>(), leftTreeQueue, rightTreeQueue, 0, 0, true);
}

public int replaceValuesToHeight(TreeNode node, ArrayDeque<ArrayDeque<TreeNode>> leftTree, ArrayDeque<ArrayDeque<TreeNode>> rightTree, ArrayDeque<TreeNode> leftTreeQueue, ArrayDeque<TreeNode> rightTreeQueue, int maxLeft, int maxRight, boolean isLeft) {
if (node == null) {
leftTreeQueue.clear();
rightTreeQueue.clear();
return 0;
}

if (isLeft)

maxLeft = replaceValuesToHeight(node.getLeft(), leftTree, rightTree, leftTreeQueue, rightTreeQueue, ++maxLeft, maxRight, true);

if (!isLeft)

maxRight = replaceValuesToHeight(node.getRight(), leftTree, rightTree, leftTreeQueue, rightTreeQueue, maxLeft, ++maxRight, false);

int depth = 1 + Math.max(maxLeft, maxRight);

if (node == getRoot()) {
leftTree.clear();
rightTree.clear();
}

node.value = depth;

//rightTreeQueue = rightTree.poll();
//leftTreeQueue = leftTree.poll();

if (maxLeft > maxRight) {
int i = 0;
while (!rightTreeQueue.isEmpty()) {
rightTreeQueue.poll().value = maxLeft - i;
i++;
}
//leftTreeQueue.clear();
} else if (maxRight > maxLeft) {
int i = 0;
while (!leftTreeQueue.isEmpty()) {
leftTreeQueue.poll().value = maxRight - i;
i++;
}
//rightTree.clear();
}

return depth;
}
```

If the TreeNode is

```class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) { ... }
public TreeNode(int val, TreeNode left, TreeNode right) { ... }
}
```

The recursive solution. Basically you need to have knowledge of the right subtree while processing the left subtree and vice-versa. The resulting value of the node depends transitively on the lowest leaf. That means you need to scan whole tree to find it (`n` operations) and only then you can assign values to the nodes.

So it depends how strong is your requirement of “single-pass” (single iteration over tree and nothing more? or making appropriate adjustment at the end so it’ll be 2*n ~= O(n)).

```static class TreeNodeDepth {
TreeNode node;
int depth;
public TreeNodeDepth(TreeNode node, int depth) { ... }
}

static class TreeNode {
int val;
TreeNode left;
TreeNode right;

public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}

@Override
public String toString() {
}

private String toString(int tabs) {
if (left == null && right == null) return val + "";
String indent = Collections.nCopies(tabs, " ").stream().collect(Collectors.joining());
return String.format("%d, %n%sl:%s,%n%sr:%s", val,
indent, left != null ? left.toString(tabs + 1) : "null",
indent, right != null ? right.toString(tabs + 1) : "null");
}
}

public static void main(String[] args) {
TreeNode root = buildExampleTree();

PriorityQueue<TreeNodeDepth> maxHeap = new PriorityQueue<>(
Comparator.<TreeNodeDepth>comparingInt(n -> n.depth).reversed()
);
System.out.println(root);

setHeights(root, 0, maxHeap);
int max = maxHeap.peek().depth; // check for: at least one element exists
while (!maxHeap.isEmpty()) {
TreeNodeDepth depthNode = maxHeap.poll();
depthNode.node.val = max - depthNode.depth + 1;
}

System.out.println(root);
}

private static void setHeights(TreeNode node, int h, PriorityQueue<TreeNodeDepth> maxHeap) {
if (node == null) return;
setHeights(node.left, h + 1, maxHeap);
setHeights(node.right, h + 1, maxHeap);
}
```

Prints:

```8,
l:3,
l:2,
l:1,
r:null,
r:1,
r:7,
l:null,
r:6,
l:1,
r:5,
l:null,
r:4,
l:null,
r:3,
l:null,
r:2,
l:null,
r:1
8,
l:7,
l:6,
l:5,
r:null,
r:6,
r:7,
l:null,
r:6,
l:5,
r:5,
l:null,
r:4,
l:null,
r:3,
l:null,
r:2,
l:null,
r:1
```
6 People found this is helpful