Binary Trees

A binary tree is a tree data structure where each node has at most two children. These children are referred to as the left child and the right child.

Key Properties of Binary Trees

• Maximum of Two Children: The defining characteristic of a binary tree is that each node in a binary tree can have zero, one, or two children. If we add a third child to any node, the tree ceases to be a binary tree.

• Single Root: Every binary tree has one unique root node, which serves as the starting point. If we were to add another root node to the tree below, it would no longer qualify as a binary tree.

• Unique Path: There is always a single, distinct path from the root node to any other node in the tree. For example, if any cycle exists or if multiple paths can be traced from the root to another node, the structure can no longer be considered a binary tree. In the example below, we can arrive at node 3 in two ways, 1 -> 2 -> 3 or 1 -> 2 -> 4 -> 3.

• Empty Tree: - Technically, an empty tree (a tree with zero nodes) is still considered a valid binary tree.

---

Representing a Binary Tree in JavaScript

In JavaScript, we can represent a binary tree using a Node class. Each Node object stores:

• val: The data or value associated with the node.
• left: A reference (pointer) to the node's left child (if any).
• right: A reference (pointer) to the node's right child (if any).

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

Let's now manually create a simple binary tree based on this image:

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(4);

Time and Space Complexities of Binary Tree Operations

In a regular binary tree, all operations like searching, insertion, and deletion have O(N) time complexity. This is because there isn't any inherent order of nodes in the tree, so you must visit every node to find the correct one. The insertion and deletion process is constant O(1), but finding where to insert the node or the node that needs to be deleted would still be O(N). If you remember, this is very similar to linked lists.

The space complexity is slightly different as it is typically O(h), where h represents the tree's height. The primary reason is that many binary tree operations are implemented recursively, and the maximum depth of the call stack corresponds to the tree height. If we use an iterative approach, the space complexity can differ depending on whether it is a depth-first or a breadth-first search, but we are getting ahead of ourselves. We'll cover this in future assignments.