Problems on Binary Tree
import java.util.LinkedList;
import java.util.Queue;
class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree {
int countOfNodes(Node root) {
if (root == null)
return 0;
return countOfNodes(root.left) + countOfNodes(root.right) + 1;
}
int sumOfNodes(Node root) {
if (root == null)
return 0;
return sumOfNodes(root.left) + sumOfNodes(root.right) + root.data;
}
int heightOfTree(Node root) {
if (root == null)
return 0;
return Math.max(heightOfTree(root.left), heightOfTree(root.right)) + 1;
}
class TreeInfo {
int heit;
int dia;
TreeInfo(int heit, int dia) {
this.heit = heit;
this.dia = dia;
}
}
TreeInfo diameterOfTree(Node root) {
if (root == null)
return new TreeInfo(0, 0);
TreeInfo left = diameterOfTree(root.left);
TreeInfo right = diameterOfTree(root.right);
int height = Math.max(left.heit, right.heit) + 1;
int diameter = Math.max(height, Math.max(left.dia, right.dia));
return new TreeInfo(height, diameter);
}
boolean isIdentical(Node root, Node subRoot) {
if (root == null && subRoot == null)
return true;
if (root == null || root == null)
return false;
if (root.data == subRoot.data)
return isIdentical(root.left, subRoot.left) && isIdentical(root.right, subRoot.right);
return false;
}
boolean isSubtree(Node root, Node subRoot) {
if (subRoot == null)
return true;
if (root == null)
return false;
if (root.data == subRoot.data)
return isIdentical(root, subRoot);
return isSubtree(root.left, subRoot.left) || isSubtree(root.right, subRoot.right);
}
void sumReplace(Node root) {
if (root == null)
return;
sumReplace(root.left);
sumReplace(root.right);
if (root.left != null)
root.data += root.left.data;
if (root.right != null)
root.data += root.right.data;
}
boolean isBalanced(Node root) {
if (root == null)
return true;
if (!isBalanced(root.left))
return false;
if (!isBalanced(root.right))
return false;
int lh = heightOfTree(root.left);
int rh = heightOfTree(root.right);
if (Math.abs(lh - rh) <= 1)
return true;
return false;
}
void rightView(Node root) {
if (root == null)
return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int idx = 0; idx < size; idx++) {
Node curr = queue.remove();
if (idx == size - 1)
System.out.print(curr.data + " ");
if (curr.left != null)
queue.add(curr.left);
if (curr.right != null)
queue.add(curr.right);
}
}
}
void leftView(Node root) {
if (root == null)
return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int idx = 0; idx < size; idx++) {
Node curr = queue.remove();
if (idx == 0)
System.out.print(curr.data + " ");
if (curr.left != null)
queue.add(curr.left);
if (curr.right != null)
queue.add(curr.right);
}
}
}
Node lowestCommonAncestor(Node root, int n1, int n2) {
if (root == null)
return null;
if (root.data == n1 || root.data == n2)
return root;
Node left = lowestCommonAncestor(root.left, n1, n2);
Node right = lowestCommonAncestor(root.right, n1, n2);
if (left == null && right == null)
return null;
else if (left != null && right != null)
return root;
else if (left != null)
return lowestCommonAncestor(root.left, n1, n2);
return lowestCommonAncestor(root.right, n1, n2);
}
int findDistance(Node root, int k, int dist) {
if (root == null)
return -1;
if (root.data == k)
return dist;
int left = findDistance(root.left, k, dist + 1);
if (left != -1)
return left;
return findDistance(root.right, k, dist + 1);
}
int distanceBtNodes(Node root, int n1, int n2) {
Node lca = lowestCommonAncestor(root, n1, n2);
int d1 = findDistance(lca, n1, 0);
int d2 = findDistance(lca, n2, 0);
return d1 + d2;
}
}
Comments
Post a Comment