Invert a Binary Search Tree (With Tests)

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.

add_alert
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.

add_alert
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);
  });