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)

   • Approach: http://javajee.com/approach-check-if-a-binary-tree-is-a-binary-search-tr...

   • Solution: http://javajee.com/problem-check-if-a-binary-tree-is-a-binary-search-tre...

2. Check if a given binary tree is balanced.

   • Assumption: Heights of two subtrees of any node should never differ by more than one, to consider a tree as balanced.

   • Solution: http://javajee.com/solution-check-if-a-binary-tree-is-balanced-in-on-time

3. Create a binary search tree with minimal height from a sorted increasing order array.

   • Solution: http://javajee.com/solution-create-a-binary-search-tree-bst-with-minimal...

4. Find difference between sum of nodes at odd levels and sum of nodes at even levels of a binary tree.

   • Difference = (Sum of nodes at odd levels) - (Sum of nodes at even levels)

   • Assumption: Root is at level 1 and left and right children of root are at level 2

   • Solution (recursive): http://javajee.com/solution-difference-between-sum-of-nodes-at-odd-level...

5.  Given a Binary Search Tree (BST), create a linked list of nodes for every level.

   • If you have a tree with depth D, you will have D linked lists.

   • Solution (recursive): http://javajee.com/solution-create-a-linked-list-of-all-nodes-at-each-le...

   • Solution (iterative): http://javajee.com/solution-create-a-linked-list-of-all-nodes-at-each-le...

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

   • Path can start or end anywhere in the tree

   • Solution: http://javajee.com/solution-find-all-paths-whose-sum-of-data-nodes-will-...

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.

Important Note!

• I will add more to the list whenever I come across a new one.

• If you were asked a problem not listed here, please let us know and we will add it here. You will also receive points. If you can provide a good solution and explanation also for your problem, you will get extra points and even cash prizes.