Binary Tree Problems.

4 min readAug 24, 2017

Hi, whoever may be reading this from the future, I hope that your journey into the wonderful world of software engineering has been awesome! Mine started a few years back, and I must say, it has definitely been one of the best experiences, to date, of my life :-)

Today, I went to an interview-prep meetup at the way-too-early time, 8:30am. The subject was Binary Trees, and we were given a few problems to solve. (Quick shout-out to Jack Wong for hosting the meetup!) Well, I solved the problems, and I thought, why not write a blog post explaining the problems, and then, the solutions that I came up with.

** Disclaimer — I am not under the impression, nor do I claim, that my solutions are the most efficient. The solutions that I came up with are just that… solutions that I came up with o_O

The Problems:

1. Build a Binary Tree (note — not a Binary Search Tree)

2. Find all paths to leaves (ie, 2–3–9, 2–3–4, 2–8–7, 2–8–1)

3. Find the longest sequential path

4. Invert the Binary Tree from the earlier problem

Give it a go! After you’ve come up with your own solutions, or at a minimum, put some thought into how you would solve these problems, check out my solutions.

The Solutions:

1. Build a Binary Tree (note — not a Binary Search Tree)

const Node = function(value) {
  this.value = value;
  this.right = null;
  this.left = null;
};

Node.prototype.insert = function(value) {
  
  let queue = [this],
      node;
  while(queue.length) {
    node = queue.shift();
    if(node.left && node.right)
      queue.push(node.left, node.right);
    else
      break;
  }

  if(!node.left)
    node.left = new Node(value);
  else
    node.right = new Node(value);
};

let root = new Node(2);
[3,8,9,4,7,1].forEach(value => root.insert(value));

A few notes on the above code…

I used a queue to populate the tree because a queue allows me to traverse level by level looking for leaves. Using this strategy, the tree will populate level by level from left to right.
Putting all of the values in an array and iterating over them is a nice way to keep your code looking clean.

2. Find all paths to leaves (ie, 2–3–9, 2–3–4, 2–8–7, 2–8–1)

Get Reuben Nahouraii’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

3. Find the longest sequential path

Decision — because problems 2 and 3 seemed to share a lot in common, I decided to use one function to do both.

const allPaths = function(node) {
  // get all paths to leaves and longest, 
  // increasing by one, sequence

  let maxSequence = 1,
   paths = [];

  const _recurse = function(node, currentSequence, currentPath) {

    if(node.value - currentPath[currentPath.length - 1] === 1)
      currentSequence++;
    else
      currentSequence = 0;

    currentPath.push(node.value);

    if(!node.left && !node.right) {
      // at a leaf, compare currentSequence to maxSequence
      if(currentSequence > maxSequence)
        maxSequence = currentSequence;

      paths.push(currentPath.slice());
      return;
    }

    if(node.left)
      _recurse(node.left, currentSequence, currentPath.slice());

    if(node.right)
     _recurse(node.right, currentSequence, currentPath.slice());
  };

  _recurse(node, 1, []);
  return {paths, maxSequence};
};

A few notes on the above code…

I’m using the slice method so that each new stack frame will have its own copy of the currentPath. Using this strategy, when the stack frame is popped off the stack, the frame under it will have a currentPath that accurately reflects its state. If currentPath was passed in without using the slice method, the underlying array would be mutated, and the state in each stack frame would be altered.

{paths, maxSequence} is equivalent to {paths: paths, maxSequence: maxSequence} — keeps the code looking clean.

If you’re finding this content helpful in some way, don’t be shy, give me a clap :-) Thanks!

4. Invert the Binary Tree from the earlier problem

const invertTree = function(node) {

  const queue = [node];
  let currentNode,
    temp;

  while(queue.length) {
    currentNode = queue.shift();
    if(!currentNode) continue;

    temp = currentNode.left;
    currentNode.left = currentNode.right;
    currentNode.right = temp;

    queue.push(currentNode.left, currentNode.right);
  }
};

A few notes on the above code…

Again, the queue is proving to be useful.
In order to test this code, I wrote a standard in-order traversal.

const traverse = function(node, arr) { // in order traversal
  if(!node) return;

  traverse(node.left, arr);
  arr.push(node.value);
  traverse(node.right, arr);
};

Then used the following code to verify that the inversion worked...

let arr = [];
traverse(root, arr);
console.log('Tree before inversion ', arr);

invertTree(root);
arr = [];
traverse(root, arr);
console.log('Tree after inversion ', arr);

And that wraps it up! If you made it this far, I commend you on your focus ;-)