What is a binary tree?

It is a recursive, non-linear tree data structure where one node is designated as the root and the others are called the children of the root. Each node has AT MOST two children.

What does each node have?

  • Each node in the tree must have:
    1. Data: Holds the value/data of the associated node
    2. Pointer to the left child
    3. Pointer to the right child.

C++ Code Example:

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

Python Code Example:

class Node:
  def __init__( self, data ):
    self.data = data;
    self.left = None;
    self.right = None;

What are ways to traverse through a binary tree?

Binary Tree Example

  1. Depth-First Search (DFS)
  • Preorder Traversal (current-left-right): You visit current node BEFORE visiting nodes from left or right subtrees. 1-2-4-5-3-6-7
  • Inorder Traversal (left-current-right): You visit current node AFTER visiting left subtree. After that, visit the right subtree. 4-2-5-1-6-3-7
  • Postorder Traversal (left-right-current): You visit current node AFTER visiting all nodes of the left and right subtrees. 4-5-2-6-7-3-1
  1. Breadth-First Search (BFS)
  • Level-Order Traversal: You visit nodes level-by-level (left-to-right fashion) at the same level. 1-2-3-4-5-6-7

What is the maximum number of nodes in a binary tree of height k?

  • (2^k+1) - 1, where k >= 1.
  • Level 1 = 3 Node; Level 2 = 7 Nodes; Level 3 = 15 …

What is the maximum number of nodes at a certain level ‘l’?

  • 2^l nodes at a certain level.