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<>();
    rightTreeQueue.add(getRoot());
    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) {
        leftTree.add(leftTreeQueue);
        rightTree.add(rightTreeQueue);
        leftTreeQueue.clear();
        rightTreeQueue.clear();
        return 0;
    }

    if (isLeft)
        leftTreeQueue.add(node);

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

    if (!isLeft)
        rightTreeQueue.add(node);


    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;
}

Answer

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() {
        return toString(1);
    }

    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;
    maxHeap.add(new TreeNodeDepth(node, h));
    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