5) Binary Tree Inversion

Pseudocode

// Pseudocode
// let tree = []
// if (!tree[0]) tree[0] = []
// tree[0].push(2)
// console.log(tree)
// -> OUtput of 2, 3, 1
// So the identification of parts of the list is like,
// i=0 is the root.
// i[1, 2] is layer one
// i[3, 4, 5, 6] is layer two
// i[7, 8, 9, 10, 11, 12, 13, 14] is layer three
//             0
//           1, 2
//        3, 4, 5, 6
// 7, 8, 9, 10, 11, 12, 13, 14

// So the pattern of layer lengths is 1, 2, 4, 8, 16, 32, etc.
// The max layers we can have, by the way, is 7, where the 7th layer isn't totally full

// I feel like all I need to do is create a tree where we have each layer organized
// as an array in an array of layers
// And then for each one after the 1st one, we flip it
// Yeah?
// Okay, at 7:33 I'm gonna go for it

// So my challenge is, at each index, I need to figure out which layer it is a part of.
// I COULD do this by just generating a list of layer lengths,
// which sure, let's do that, and just cap it out

Implementation

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
 
 
  let tree = []
  let layerLengths = [1, 2, 4, 8, 16, 32, 64, 128]
  layer = 0
 
  for (let i = 0; i < root.length; i++){
    if (!tree[layer]) tree[layer] = []
    tree[layer].push(root[i])
    // So we push the current layer, and then we check and see...
    // Is the current layer now the max length it should be according to layer lengths?
    // if so, we just add another layer
    // Which we will now push to.
    if (tree[layer].length === layerLengths[layer]){
      layer++
    }
  }
 
  // Handle case where last layer is not full
  // But only do so if last layer is VALID, since we layer++ to a layer that may not exist
  // in cases where a layer is perfectly full
  if (tree[layer]){
    let valenceLength = tree[layer].length
    let diff = layerLengths[layer] - valenceLength
    let compensation = new Array(diff)
    tree[layer].concat(compensation)
  }
 
  for (layer of tree){
    layer.reverse()
  }
 
  return tree
 
    
};
 
console.log(invertTree([4,2,7,1,3,6,9]))
 

I’ve never worked with binary trees before, and so mistake made involved missing the fundamental domain of the question of itself and no actually working with a binary tree data structure at all. I ended up returning an array instead.

While I am proud that the array I returned is, I believe, in the right order to implement the binary tree this exercise asks for, it’s not a binary tree. At least not by the definition of the question.

I think that a class could be written that would be able to content with this similarly to how a binary tree would function while still maintaining that single array as the source of truth for the data structure.

What I’m not sure about is which is more performant - this abstract binary tree I created that refers to indexes in a single list, or true binary tree.

To move forward, I see two paths

• Stubbornly stick to my weirdly unique idea of what a binary tree is and just construct one out of the reversal I’ve created myself
• Create the binary tree from the data, and then just reverse the left and right values

These approaches are that different - they mostly just involve learning how to construct a binary tree out of a list using javascript.

What…it would right?

    1
   4, 5
6, 7, 4, 2

If I swapped right and left values of the above tree, I’d get:

   1
  5, 4
2, 4, 7, 6

Yeah that works.

Okay so I tried to create a recursive tree:

let root = [1, 4, 2, 5, 5, 7, 2, 3]

class TreeNode{
  constructor(val, left, right){
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
  }
}

function recursiveTree(source, index){
  if (index >= source.length) return // don't try to create a leaf if no values left
  let node = new TreeNode(
    source[0 + index],
    index+1 >= source.length ? null : recursiveTree(source, index+1),
    index+2 >= source.length ? null : recursiveTree(source, index+2)
   )
  if (index === 0) return node
}

console.log(recursiveTree(root, 0))

I made some pretty serious mistakes. Here they are as far as I can tell:

1. Checking against an out of bound index twice (or debatably thrice) - at the beginning of the recurse function AND inside of the new TreeNode. This might even cause an error, since I’m not even checking if the index is null despite checking it explicitly as null
2. 0 + index is a silly thing to do - not a problem, but there’s no reason to add anything to 0
3. Only returning the node when index === 0 was a mis-use of a recursive function - each successive recursion needs to return; that’s how the tree is built. I’m not editing a tree in place
4. Only adding 1 or adding 2 to the index isn’t enough. It is for the first generation of children, when we add 1 or 2 to 0 to get 1 and 2 as the values for the next generation. But if we add 1 to the first generation value of 1 we get 2, which is also in generation 1. This will lead us trying to create a generation 2 that has 2 of the same indexes as those in generation 1 - not sure if this leads to infinite recursion, but it will create a janky, redundant binary tree. Rather than each element getting its own node, each element will, I think, get two nodes each, which is not what we want.

If we fix the code it looks like this:

let root = [1, 4, 2, 5, 5, 7, 2, 3]
 
class TreeNode{
  constructor(val, left, right){
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}
 
function recursiveTree(source, index){
  if (index >= source.length) return null // Return null if no values left
  
  // Create the node with its left and right children
  let node = new TreeNode(
    source[index],
    recursiveTree(source, 2 * index + 1),
    recursiveTree(source, 2 * index + 2)
  )
  
  return node // Always return the node
}
 
console.log(recursiveTree(root, 0))
 

And creates this binary tree:

Except it doesn’t because I still have a few more mistakes.

class TreeNode{
  constructor(val, left, right){
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}
 
function invertTree(source, index){
 
  if (index >= source.length || source[index] === null) return null
  
  // Create the node with its left and right children
  return new TreeNode(
    source[index],
    invertTree(source, index * 2 + 2),
    invertTree(source, index * 2 + 1),
  )
  
}
 
console.log(invertTree([4,2,7,1,3,6,9], 0))

I needed to add the if (...source[index] === null) return null condition. The index >= source.length conditions covers issues where we have run out of values, but it is also very possible to NOT have a fully packed final generation, in which case we are…no that’s not it. Because this example has no nulls. So this should work.

var invertTree = function(root) {
  // base case
  if(!root) return null;
  const t3 = new TreeNode();
 
  //recursive case
  t3.val = root.val;
  t3.left = invertTree(root.right);
  t3.right = invertTree(root.left);
  return t3;
};

Turns out I definitely misunderstood a couple things. I am being given a tree to begin with. 🤦🏻‍♂️

Conclusion

• I now know how to create a binary tree
• I didn’t need to create a binary tree for this challenge at all, just interact with existing ones