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.

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

     1
    / \
   2   3
  / \ 
 4   5

Node class (.left, .right, .value)

class TreeNode<E> {
   private E value;
   private TreeNode left;
   private TreeNode right;
}

Tree Terms

  • Root node (similar to head node in Linked Lists, represents start of the tree)

  • Leaf nodes (nodes with no child nodes, both left and right are null)

  • Depth (# of edges from root to node)

  • Height (# of edges from node to lowest leaf node)

Other Tree Terms

  • Complete Binary Tree (Tree is filled left to right, last level does not have to be completely filled)

  • Perfect Binary Tree (Tree is filled left to right including last level)

Intro: Tree Traversal

Depth First Traversals - Travels down on a single branch at a time

  • In-Order Traversal (left node -> current node -> right node)
  • Pre-Order Traversal (current node -> left node -> right node)
  • Post-Order Traversal (left node -> right node -> current node)

Breadth First Traversal - Goes down one level at a time from top to bottom.

  • Level Order Traversal

1) In-Order Traversal Printing

Given the root of a binary tree, print the content of a binary tree, using in-order traversal.

Input:    2
         / \
        1   4
           / \
          3   5

Output: 1,2,3,4,5

Time: O(n)
Space: O(1)

2) Post-Order Traversal Printing

Given the root of a binary tree, print the content of a binary tree, using post-order traversal.

Input:    5
         / \
        1   4
           / \
          2   3

Output: 1,2,3,4,5

Time: O(n)
Space: O(1)

3) Binary Leaves List

Form a singly linked list from the leaves (bottom nodes) of a binary tree.

Input:    2
         / \
        1   4
           / \
          3   5

Output: 1 -> 3 -> 5

Time: O(n)
Space: O(n)

4) Check Balanced Binary Tree

A balanced tree is a tree whose left sub-tree and right-tree have a height difference of 1 (or 0). Given a root node, return true if the tree is balanced, false otherwise.

Input:     1
          / \
         2   3
        /
       4
Output: True

Input:    1
         / \
        2   3
       /
      4
       \
        5
Output: False

Time: O(n)		// Brute force is O(n^2)
Space: O(1)

5) Validate a BST

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.
Input: root = [2,1,3]
     2
    / \
   1   3
Output: true

Input: root = [5,1,4,null,null,3,6]
     5
    / \
   1   4
      / \
     3   6
Output: false

Time: O(n)
Space: O(1)

Trial Problems

1) Count Nodes

Given the root of a binary tree, return integer array levels that contains the number of nodes in each level.

Input: root = null
Output: [0]

Input: root =
     5
      \
       4
      / \
     3   6
Output: [1, 1, 2]

Input: root =
      5
    /   \
   4     1
  / \   / \
 4   2 3   1
Output: [1, 2, 4]

Try to return an array with length equal to the tree’s height

2) Partially Sorted Binary Tree

Given the root of a perfect binary tree, return the binary tree with each level sorted least to greatest (left to right).

Input: root = 
      5
    /   \
   4     1
  / \   / \
 4   2 3   1
Output: 
      5
    /   \
   1     4
  / \   / \
 1   2 3   4

Hint: How can I access each node on a specific level?