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

Question

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

Create a new TreeNode
Assign root->left to ->right
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()?

Because it's the same root. All the changes made (via queue) are to the nodes of the original tree. Referencing objects is by using pointers so if you change it one place, all the other places pointing to the object will get the updated value, since it's the same object. This is different than numbers and strings. — IT goldman
– IT goldman, Commented Jul 2, 2022 at 17:54

testing_22 · Accepted Answer · 2022-07-02 18:17:42Z

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.

Adrian Mole · Accepted Answer · 2022-07-04 07:33:25Z

1

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.

edited Jul 4, 2022 at 7:33

Adrian Mole

52.1k193 gold badges61 silver badges101 bronze badges

answered Jul 2, 2022 at 18:36

LIE AND DIE

111 bronze badge

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related