Java - Binary Trees
Java - DSA
Trees
1. Build Tree from given Preorder Sequence
//Build a Tree from its Preorder traversal
public class BinaryTreesYT {
static class Node {
int data;
Node left;
Node right;
Node(int data) {
[Link] = data;
[Link] = null;
[Link] = null;
}
}
static class BinaryTree {
static int idx = -1;
public static Node buildTree(int nodes[]) {
idx++;
if(nodes[idx] == -1) {
return null;
}
Node newNode = new Node(nodes[idx]);
[Link] = buildTree(nodes);
[Link] = buildTree(nodes);
return newNode;
}
}
public static void main(String args[]) {
int nodes[] = {1, 2, 4, -1, -1, 5, -1, -1, 3, -1, 6, -1, -1};
BinaryTree tree = new BinaryTree();
Node root = [Link](nodes);
[Link]([Link]);
}
}
Java - Binary Trees
2. Tree Traversals
a. Preorder
public static void preorder(Node root) {
if(root == null) {
[Link](-1+" ");
return;
}
[Link]([Link]+" ");
preorder([Link]);
preorder([Link]);
}
b. Inorder
public static void inorder(Node root) {
if(root == null) {
[Link](-1+" ");
return;
}
inorder([Link]);
[Link]([Link]+" ");
inorder([Link]);
}
c. Postorder
public static void postorder(Node root) {
if(root == null) {
[Link](-1+" ");
return;
}
postorder([Link]);
postorder([Link]);
[Link]([Link]+" ");
}
d. Level Order
public static void levelOrder(Node root) {
if(root == null) {
return;
}
Queue<Node> q = new LinkedList<>();
[Link](root);
[Link](null);
while(![Link]()) {
Node curr = [Link]();
Java - Binary Trees
if(curr == null) {
[Link]();
//queue empty
if([Link]()) {
break;
} else {
[Link](null);
}
} else {
[Link]([Link]+" ");
if([Link] != null) {
[Link]([Link]);
}
if([Link] != null) {
[Link]([Link]);
}
}
}
}
3. Height of Tree
public static int height(Node root) {
if(root == null) {
return 0;
}
int leftHeight = height([Link]);
int rightHeight = height([Link]);
return [Link](leftHeight, rightHeight) + 1;
}
4. Count of Nodes of Tree
public static int countOfNodes(Node root) {
if(root == null) {
return 0;
}
int leftNodes = countOfNodes([Link]);
int rightNodes = countOfNodes([Link]);
return leftNodes + rightNodes + 1;
}
5. Sum of Nodes of Tree
public static int sumOfNodes(Node root) {
Java -if(root
Binary== Trees
null) {
return 0;
}
int leftSum = sumOfNodes([Link]);
int rightSum = sumOfNodes([Link]);
return leftSum + rightSum + [Link];
}
6. Diameter of Tree - Approach1 O(N^2)
public static int diameter(Node root) {
if(root == null) {
return 0;
}
int diam1 = height([Link]) + height([Link]) + 1;
int diam2 = diameter([Link]);
int diam3 = diameter([Link]);
return [Link](diam1, [Link](diam2, diam3));
}
7. Diameter of Tree - Approach2 O(N)
public static TreeInfo diameter(Node root) {
if(root == null) {
return new TreeInfo(0, 0);
}
TreeInfo leftTI = diameter([Link]);
TreeInfo rightTI = diameter([Link]);
int myHeight = [Link]([Link], [Link]) + 1;
int diam1 = [Link] + [Link] + 1;
int diam2 = [Link];
int diam3 = [Link];
int myDiam = [Link](diam1, [Link](diam2, diam3));
return new TreeInfo(myHeight, myDiam);
}
8. Subtree of another tree
public boolean isIdentical(TreeNode root,TreeNode subRoot){
if(subRoot == null && root == null){
return true;
}
Java -if(root
Binary== Trees
null || subRoot == null){
return false;
}
if([Link] == [Link]){
return isIdentical([Link], [Link]) && isIdentical([Link],
[Link]);
}
return false;
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(subRoot == null){
return true;
}
if(root == null){
return false;
}
if(isIdentical(root, subRoot)){
return true;
}
return isSubtree([Link], subRoot) || isSubtree([Link], subRoot);
}