Nanthakumar

sunny icon
We're HIRING at Sentry! Get in front of our recruiters!
Invert a Binary Search Tree (With Tests)

A solution to the infamous interview question.

We are going to start the problem by creating a Node class that we will use to build our binary tree.

First let's create the constructor for the Node class. It will have the data, left and right properties. For a new node, we will initialize the left and right properties as null

class Node {
constructor(data) {
this.data = data
this.left = null
this.right = null
}
}

Now, let's create the insert method for the Node class.

If a new piece of data is less than the node, it will be inserted to the left. If the data is greater than the node, it will be inserted to the right. We will have to continue this operation, starting from the root node until we find a left or right property that is null.

Use recursion.
  insert(data, node = this) {
if (data > node.data) {
if (!node.right) {
return (node.right = new Node(data))
} else {
return this.insert(data, node.right)
}
}
if (data < node.data) {
if (!node.left) {
return (node.left = new Node(data))
} else {
return this.insert(data, node.left)
}
}
}

Now let's write a method that can invert the tree.

So to invert the tree, we will need to flip the right and left properties of each node. We will continue flipping the properties until we reach a node where both right and left properties are null.

More recursion.
  invertTree(node = this) {
let temp = node.left
node.left = node.right
node.right = temp
if (node.left) {
this.invertTree(node.left)
}
if (node.right) {
this.invertTree(node.right)
}
return node
}

Test the insert and invertTree methods.

  test('Node can insert correctly', () => {
const node = new Node(10);
node.insert(5);
node.insert(15);
node.insert(17);

expect(node.left.data).toEqual(5);
expect(node.right.data).toEqual(15);
expect(node.right.right.data).toEqual(17);
});

test("Returns inverted tree", () => {
const node = new Node(10);
node.insert(5);
node.insert(15);
node.insert(17);
node.invertTree()
expect(node.left.left.data).toEqual(17);
});