Invert Binary Tree Js Leet problem - confused about the returned variable

user_15453019 0
Viewed 55

So there is this problem essentially, What we are doing to invert the Tree is

  1. Create a new TreeNode
  2. Assign root->left to ->right
  3. Assign root->right to ->left

The solution is

function invertTree(root) {
  const queue = [root];
  while (queue.length) {
    const n = queue.pop();
    if (n != null) {
      [n.left, n.right] = [n.right, n.left];
      queue.push(n.left, n.right);
    }
  }
  return root;
};

However, the part I am confused about is the change was made to queue not to root. why are we returning root at the end? It seems like we have direct access to the reference of the initial root. I thought the root inside the queue is a copy of the root. that's the part I am confused about. why is it a reference and not a copy? is it because we have not used new Array()?

javascript
2 Answers

As the problem states, you must return the root. But before that, you have to invert it.

The logic is to keep an array named queue that stores the next TreeNode to be inverted and it does that iteratively inside a while-loop.

Firstly, the algorithm starts with the queue filled with the root, so const queue = [root].

Then, it gets the last element of the queue (with .pop()), and if it's not a null node, call it n and inverse its left and right branches by doing: [n.left, n.right] = [n.right, n.left]. This is the moment where we make changes to the root.

By popping it from the queue, we have direct access to the reference of the initial root object, and whichever changes we do to their nodes affect it.

Later, the algorithm pushes to the queue the left and right nodes from root to be inverted. It makes the loop run again performing the same logic in each branch. Eventually, it always points to a node that references root, which explains why it changes indirectly.

It stops running when the queue length is 0, which is when the queue doesn't get nodes pushed anymore meaning the tree was inverted successfully.

user_120969220

If you look closely, the tree is being inverted in your while loop and the queue is just working as a supporting data structure … that's why you are returning the root after the tree is inverted.

user_194687130
Related