Intro: Binary Tree Data Structure

A binary tree is a tree data structure in which each node can have at most two children, which are referred to as the left child and the right child.

The topmost node in a binary tree is called the root, and the bottom-most nodes are called leaves.

A binary tree can be visualized as a hierarchical structure with the root at the top and the leaves at the bottom.

Each node in the tree contains the following:

  • Data
  • Pointer to the left child
  • Pointer to the right child
     1
    / \
   2   3
  / \ 
 4   5

Example of tree node with integer data (Java)

// Class containing a node with a left and right child and some data
class Node {
    int data;
    Node left, right;
 
    public Node(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);

1) Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

Input:      3
           / \
          9  20
            /  \
           15   7
Output: 3

Example 2:

Input:   1
          \
           2
Output: 2

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -100 <= Node.val <= 100

2) Evaluate Boolean Binary Tree

You are given the root of a full binary tree with the following properties:

  • Leaf nodes have either the value 0 or 1, where 0 represents False and 1 represents True.
  • Non-leaf nodes have either the value 2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND.

The evaluation of a node is as follows:

  • If the node is a leaf node, the evaluation is the value of the node, i.e. True or False.
  • Otherwise, evaluate the node’s two children and apply the boolean operation of its value with the children’s evaluations.

Return the boolean result of evaluating the root node.

A full binary tree is a binary tree where each node has either 0 or 2 children.

A leaf node is a node that has zero children.

Example 1:

Input:        2          AKA:       OR
             / \                   /  \  
            1   3               True   AND
               / \                    /   \
              0   1                False  True
Output: true
Explanation:
The AND node evaluates to False AND True = False.
The OR node evaluates to True OR False = True.
The root node evaluates to True, so we return true.

Example 2:

Input:   0 
Output: false
Explanation: The root node is a leaf node and it evaluates to false, so we return false.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 3
  • Every node has either 0 or 2 children.
  • Leaf nodes have a value of 0 or 1.
  • Non-leaf nodes have a value of 2 or 3.

3) Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input:      p           q 
            1           1
           / \         / \  
          2   3       2   3
Output: true

Example 2:

Input:      p           q 
            1           1
           / \         / \  
          2   1       1   2
Output: false

Constraints:

  • The number of nodes in both trees is in the range [0, 100].
  • -10^4 <= Node.val <= 10^4

4) Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input:         3
            /     \
          5        1
        /  \     /   \
       6    2   0     8
           / \
          7   4
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input:         3
            /     \
          5        1
        /  \     /   \
       6    2   0     8
           / \
          7   4
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Constraints:

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.