Java Binary Tree and Graph Algorithm Practice
Practice Problems
1. Check if a Binary Tree is a Mirror of Itself
The idea is to write a recursive function isMirror() that takes two trees as arguments and returns true if the trees are mirrors and false if they are not. The isMirror() function recursively checks two roots and the subtrees under those roots.
// Java program to check if a binary tree is symmetric or not
class Node {
int key;
Node left, right;
Node(int item) {
key = item;
left = right = null;
}
}
class BinaryTree {
Node root;
// Returns true if trees with roots as node1 and node2 are mirrors
boolean isMirror(Node node1, Node node2) {
// If both trees are empty, then they are mirror images
if (node1 == null && node2 == null)
return true;
// For two trees to be mirror images, the following three
// conditions must be true
// 1 - Their root node's key must be the same
// 2 - Left subtree of left tree and right subtree
// of right tree have to be mirror images
// 3 - Right subtree of left tree and left subtree
// of right tree have to be mirror images
if (node1 != null && node2 != null && node1.key == node2.key)
return (isMirror(node1.left, node2.right)
&& isMirror(node1.right, node2.left));
// If neither of the above conditions is true then
// node1 and node2 are not mirror images
return false;
}
// Returns true if the tree is symmetric i.e. mirror image of itself
boolean isSymmetric(Node node) {
// Check if tree is mirror of itself
return isMirror(root, root);
}
// Driver program
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(2);
tree.root.left.left = new Node(3);
tree.root.left.right = new Node(4);
tree.root.right.left = new Node(4);
tree.root.right.right = new Node(3);
boolean output = tree.isSymmetric(tree.root);
if (output == true)
System.out.println("1");
else
System.out.println("0");
}
}2. Find the Largest Value in Each Tree Row
BFS Approach: Insert elements into a queue row by row (root then children).
- Enqueue root node; temp = root, queue size = 1. Traverse queue until queue size is met. Add root to ArrayList (output).
- Enqueue next row’s n nodes; queue size = n. Traverse queue until queue size is met. If current > temp, replace temp (max).
- Continue until no more rows.
public List<Integer> largestValueInRow(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
int largest = Integer.MIN_VALUE;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
largest = Math.max(largest, node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(largest);
}
return result;
}3. Clone an Undirected Graph
The idea is to do a BFS traversal of the graph and while visiting a node, make a clone node of it (a copy of the original node). If a node is encountered which is already visited, then it already has a clone node.
class Graph {
// A method which clones the graph and
// returns the reference of the new cloned source node
public GraphNode cloneGraph(GraphNode source) {
Queue<GraphNode> q = new LinkedList<>();
q.add(source);
// A HashMap to keep track of all the
// nodes which have already been created
HashMap<GraphNode, GraphNode> hm = new HashMap<>();
// Put the node into the HashMap
hm.put(source, new GraphNode(source.val));
while (!q.isEmpty()) {
// Get the front node from the queue
// and then visit all its neighbors
GraphNode u = q.poll();
// Get corresponding cloned graph node
GraphNode cloneNodeU = hm.get(u);
if (u.neighbors != null) {
Vector<GraphNode> v = u.neighbors;
for (GraphNode graphNode : v) {
// Get the corresponding cloned node
// If the node is not cloned then we will
// simply get a null
GraphNode cloneNodeG = hm.get(graphNode);
// Check if this node has already been created
if (cloneNodeG == null) {
q.add(graphNode);
// If not then create a new node and
// put into the HashMap
cloneNodeG = new GraphNode(graphNode.val);
hm.put(graphNode, cloneNodeG);
}
// Add the 'cloneNodeG' to neighbor
// vector of the cloneNodeU
cloneNodeU.neighbors.add(cloneNodeG);
}
}
}
// Return the reference of cloned source node
return hm.get(source);
}
}4. Print All Root-to-Leaf Paths
Use a path array path[] to store the current root-to-leaf path. Traverse from the root to all leaves in a top-down fashion. While traversing, store the data of all nodes in the current path in the array path[]. When we reach a leaf node, print the path array.
// Java program to print all the node-to-leaf paths
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
/* Given a binary tree, print out all of its root-to-leaf
paths, one per line. Uses a recursive helper to do
the work. */
void printPaths(Node node) {
int path[] = new int[1000];
printPathsRecur(node, path, 0);
}
/* Recursive helper function -- given a node, and an array
containing the path from the root node up to but not
including this node, print out all the root-leaf paths. */
void printPathsRecur(Node node, int path[], int pathLen) {
if (node == null)
return;
/* Append this node to the path array */
path[pathLen] = node.data;
pathLen++;
/* It's a leaf, so print the path that led to here */
if (node.left == null && node.right == null)
printArray(path, pathLen);
else {
/* Otherwise try both subtrees */
printPathsRecur(node.left, path, pathLen);
printPathsRecur(node.right, path, pathLen);
}
}
/* Utility function that prints out an array on a line. */
void printArray(int ints[], int len) {
int i;
for (i = 0; i < len; i++) {
System.out.print(ints[i] + " ");
}
System.out.println("");
}
// Driver program to test above functions
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(10);
tree.root.left = new Node(8);
tree.root.right = new Node(2);
tree.root.left.left = new Node(3);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(2);
/* Test the built tree by printing paths */
tree.printPaths(tree.root);
}
}5. Sum of All Numbers Formed from Root-to-Leaf Paths
The idea is to do a preorder traversal of the tree. In the preorder traversal, keep track of the value calculated until the current node; let this value be val. For every node, we update the val as val * 10 plus the node’s data.
// Java program to find sum of all numbers formed from root
// to leaf paths
class Node {
int data;
Node left, right;
Node(int item) {
data = item;
left = right = null;
}
}
class BinaryTree {
Node root;
// Returns sum of all root-to-leaf paths. The 1st parameter is
// root of current subtree, the 2nd parameter is the value of the
// number formed by nodes from root to this node
int treePathsSumUtil(Node node, int val) {
// Base case
if (node == null)
return 0;
// Update val
val = (val * 10 + node.data);
// If current node is leaf, return the current value of val
if (node.left == null && node.right == null)
return val;
// Recur sum of values for left and right subtree
return treePathsSumUtil(node.left, val)
+ treePathsSumUtil(node.right, val);
}
// A wrapper function over treePathsSumUtil()
int treePathsSum(Node node) {
// Pass the initial value as 0 as there is nothing above root
return treePathsSumUtil(node, 0);
}
// Driver program to test above functions
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(6);
tree.root.left = new Node(3);
tree.root.right = new Node(5);
tree.root.right.right = new Node(4);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
tree.root.left.right.right = new Node(4);
tree.root.left.right.left = new Node(7);
System.out.print("Sum of all paths is " +
tree.treePathsSum(tree.root));
}
}6. Course Schedule: Can You Finish All Courses?
Given the total number of courses and a list of all prerequisite pairs, is it possible for you to finish all courses? Using BFS:
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null) {
throw new IllegalArgumentException("Illegal prerequisites array");
}
int len = prerequisites.length;
if (numCourses == 0 || len == 0) {
return true;
}
// Counter for number of prerequisites
int[] pCounter = new int[numCourses];
for (int i = 0; i < len; i++) {
pCounter[prerequisites[i][0]]++;
}
// Store courses that have no prerequisites
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (pCounter[i] == 0) {
queue.add(i);
}
}
// Number of courses that have no prerequisites
int numNoPre = queue.size();
while (!queue.isEmpty()) {
int top = queue.remove();
for (int i = 0; i < len; i++) {
// If a course's prerequisite can be satisfied by a course in queue
if (prerequisites[i][1] == top) {
pCounter[prerequisites[i][0]]--;
if (pCounter[prerequisites[i][0]] == 0) {
numNoPre++;
queue.add(prerequisites[i][0]);
}
}
}
}
return numNoPre == numCourses;
}