Coding Interview Club

Prepare for coding interviews in simple and structured steps

Important Problems on Trees and Graphs for Interviews and Self Assessment

Category: 
Problem: 

I will list down some problems on the topic of trees and graphs that are commonly asked in interviews. Please revise topics on tress such as Binary Trees, Binary Search Tree (BST), Balancing a Tree, Full and Complete Trees, Binary Tree Traversals (recursive), Tries, Depth First Search (DFS), Breadth First Search (BFS).

 

Problems

Trees

  1. Check if a binary tree is a Binary Search Tree (BST)
  2. Check if a given binary tree is balanced.
  3. Create a binary search tree with minimal height from a sorted increasing order array.
  4. Find difference between sum of nodes at odd levels and sum of nodes at even levels of a binary tree.
  5.  Given a Binary Search Tree (BST), create a linked list of nodes for every level.
  6. Given a binary tree with an integer data element; find all paths whose sum of data nodes will be equal to a given value
  7. Check if a binary tree (T2) is a sub tree of another tree (T1)
    • T1 has millions of nodes and T2 has hundreds of nodes
  8.  Find the inorder successor (next node) of a given node in a Binary Search Tree (BST)?
    • Each node has a link to its parent
  9. Find the first common ancestor of two nodes in a binary tree
    • Avoid storing additional nodes in any data structure
    • The binary tree might not be a Binary Search Tree (BST)
  10. Traverse the tree in spiral (zig zag) form and print nodes.
    • Consider below tree levels:
      • 1
      • 2 3
      • 4 5 6 7
      • 8 9
    • Result should be: 1 3 2 4 5 6 7 9 8

 

Graphs

  1. Find out if there is a route between two nodes in a directed graph.
Solution: 

Refer to individual problems under corresponding problem category for solutions.

Back to Top