insert

inOrder

Walkthrough

A binary tree is a tree data structure where each node has at most two children, left and right. The inorder traversal of a binary tree is a way to visit each node of the tree in a specific order. The order is: traverse the left subtree, visit the root, then traverse the right subtree. This way of traversal is the most commonly used way to visit nodes in a binary tree.

To perform an inorder traversal, we can use recursion. We will start at the root node, check if it is not null, then we will visit the left subtree recursively, then we will visit the current node, and finally, we will visit the right subtree recursively.

Here is the code for the solution:

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

class BinaryTree {
  constructor() {
    this.root = null;
  }

  insert(data) {
    const newNode = new Node(data);
    if (this.root === null) {
      this.root = newNode;
      return;
    }
    this.insertNode(this.root, newNode);
  }

  insertNode(node, newNode) {
    if (newNode.data < node.data) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  inOrder(node) {
    if (node !== null) {
      this.inOrder(node.left);
      console.log(node.data);
      this.inOrder(node.right);
    }
  }
}

const tree = new BinaryTree();
tree.insert(60);
tree.insert(125);
tree.insert(30);
tree.insert(33);
tree.insert(73);
tree.insert(40);
tree.insert(20);
tree.insert(90);

tree.inOrder(tree.root);

Expected output:

20 30 33 40 60 73 90 125

The above code defines the Node and BinaryTree classes. We insert data into the binary tree using the insert method. We also define the insertNode method to traverse the tree and find the correct position to insert a new node. Finally, we define the inOrder method to perform the inorder traversal.

We create an instance of the BinaryTree class and insert some data into the tree. Then we call the inOrder method on the tree with the root node as the starting point. The inOrder method prints the data of the nodes in the tree in the order of traversal.

Big O Complexity Analysis:

The time complexity of the inorder traversal of a binary tree is O(n) because we need to visit each node of the tree once. The space complexity of the inorder traversal is also O(n) because we use a recursive call stack to visit the nodes. In the worst-case scenario, the height of the tree is equal to the number of nodes, which leads to O(n) space complexity.

In the above code, we use recursion to traverse the tree. Since we are visiting each node once, the time complexity of the inOrder method is also O(n). The space complexity of the inOrder method is O(h), where h is the height of the tree. If the tree is balanced, the height of the tree is log(n), which leads to O(log(n)) space complexity. However, if the tree is unbalanced, the height of the tree is equal to the number of nodes, which leads to O(n) space complexity.