Up to date

public class AVLTree { private static Node root; static Node insert(Node node, int data) { // if node is null then create a node and return if(node == null) { return new Node(data); } else if(data node.data) { // insert into right sub tree node.right = insert(node.right, data); } // set height of current node node.height = getHeightOfNode(node); // check the balance factor to perform rotation of tree if(getBalanceFactor(node) == 2) { if(getBalanceFactor(node.left) == 1) { return performLLRotation(node); } else if(getBalanceFactor(node.left) == -1) { return performLRRotation(node); } } else if(getBalanceFactor(node) == -2) { if(getBalanceFactor(node.right) == -1) { return performRRRotation(node); } else if(getBalanceFactor(node.right) == 1) { ...

It's height balanced tree Height is balanced by balance factor. Balance factor (BF) = height of left sub tree - height of right sub tree Valid FB values = {-1, 0, 1}. BF = |lh-rh| <= 1 Node is balanced if |lh-rh| <= 1 Node is unbalanced if |lh-rh| > 1 All rotations : 1. Left Left (LL) Rotation 2. Right Right (RR) Rotation 3. Left Right (LR) Rotation 4. Right Left (RL) Rotation Idea behind rotations : Insert and delete program   Height vs Node analysis

Reference import java.util.ArrayDeque; class ConstructBSTGivenPreorder { private static Node root; static void constructFromPreorderIterative(int[] preorder) { // create root root = new Node(preorder[0]); // create statck to track left child of tree during construction of tree ArrayDeque stack = new ArrayDeque (); // taking variable to track current node Node current = root; // insert all elements for(int i = 1; i stack.peekFirst().data) { current = stack.peekFirst(); // stack.peek stack.pollFirst(); // stack.pop } current.right = node; current = node; } } } static void constructFromPreorderIterative2(int[] preorder) { // create root root = new Node(preorder[0]); // create statck to track left child of tree during constr...

Reference import java.util.ArrayDeque; class BinaryTree { private static Node root; static Node insertRecursive(Node current, Node previous, int data) { if(current == null) { Node node = new Node(data); if(previous == null) { // it's first node in tree return node; } else if(data current.data) { current.right = insertRecursive2(current.right, data); } return current; } static Node insert(Node node, int data) { Node newNode = new Node(data); // if tree is empty if(node == null) { return newNode; } Node previous, current; current = previous = node; // iterate thorugh tree until don't find element or reach to end while(current != null) { if(current.data == data) { // data exists in the tree return node; } ...

import java.util.ArrayDeque; class SearchTree { static boolean searchRecursive(Node root, int data) { // base check if(root == null) { return false; } else if(root.data == data) { return true; } else if(data Output The inorder traversal is 0 2 3 4 5 6 7 The preorder traversal is 4 2 0 3 5 6 7 Tree contains 3 : true Tree contains 7 : true Tree contains 80 : false Tree contains 3 : true Tree contains 7 : true Tree contains 80 : false

import java.util.ArrayDeque; class ConstructTree { static int count(Node root) { if(root != null) { int leftCount = count(root.left); int rightCount = count(root.right); return leftCount + rightCount + 1; } return 0; } static Node construct(int[] preOrder, int[] inOrder) { // base check if (preOrder.length == 0 || preOrder.length != inOrder.length) { return null; } // counters int preOrderIndex = 0; int inOrderIndex = 0; ArrayDeque stack = new ArrayDeque (); Node root = new Node(preOrder[preOrderIndex]); stack.addFirst(root); preOrderIndex++; while(!stack.isEmpty()) { Node top = stack.peekFirst(); if(top.data == inOrder[inOrderIndex]) { stack.pollFirst(); inOrderIndex++; // if all ...

Iterative version reference. import java.util.ArrayDeque; class ConstructTree { static Node construct(int[] preOrder, int[] inOrder) { // base check if (preOrder.length == 0 || preOrder.length != inOrder.length) { return null; } // counters int preOrderIndex = 0; int inOrderIndex = 0; ArrayDeque stack = new ArrayDeque (); Node root = new Node(preOrder[preOrderIndex]); stack.addFirst(root); preOrderIndex++; while(!stack.isEmpty()) { Node top = stack.peekFirst(); if(top.data == inOrder[inOrderIndex]) { stack.pollFirst(); inOrderIndex++; // if all the elements in inOrder have been visted, we are done if (inOrderIndex == inOrder.length) { break; } // Check if there are...

Iterative version. import java.util.concurrent.atomic.AtomicInteger; import java.util.Map; import java.util.HashMap; class ConstructTree { static Node constructRecursive(int[] preorder, Map inorderElementMap, AtomicInteger inorderCounter, int inStartIndex, int inEndIndex) { // Corner case for leaf nodes if(inStartIndex > inEndIndex) { return null; } Node root = new Node(preorder[inorderCounter.getAndIncrement()]); // get the root node index in sequence `inorder[]` to determine the // left and right subtree boundary int index = inorderElementMap.get(root.data); // construct left sub-tree root.left = constructRecursive(preorder, inorderElementMap, inorderCounter, inStartIndex, index-1); // construct right sub-tree root.right = constructRecursive(preorder, inorderElementMap, inorderCounter, index+1, inEndIndex); ...

import java.util.Queue; import java.util.LinkedList; class LevelOrderTreeTraversal { private static Node root; void leverOrderUsingQueue(Node root) { if(root == null) { return; } Queue queue = new LinkedList (); queue.add(root); Node current; while(!queue.isEmpty()) { // dequeue from queue current = queue.poll(); System.out.print(current.data + " "); // enqueue left node if(current.left != null) { queue.add(current.left); } // enqueue right node if(current.right != null) { queue.add(current.right); } } } /** * Time to print n levels is O(n^2) */ void leverOrderUsingRecursion(Node root) { if(root == null) { return; } int height = height(root); for(int i = 0; i 0) { ...

import java.util.Stack; class BinaryTree { private static Node root; /** * a) print it * b) push its right child * c) push its left child */ void preOrder(Node root) { if(root != null) { Stack stack = new Stack (); Node current; stack.push(root); while(!stack.empty()){ // Pop the top item from stack and print it current = stack.pop(); System.out.print(current.data + " "); // Push right and left children of the popped node to stack if(current.right != null) { stack.push(current.right); } if(current.left != null) { stack.push(current.left); } } } } void inOrder(Node root) { if(root == null) { return; } Stack stack = new Stack (); // start...

class BinaryTree { private static Node root; void preOrder(Node root) { if(root != null) { System.out.print(root.data + " "); preOrder(root.left); preOrder(root.right); } } void inOrder(Node root) { if(root != null) { inOrder(root.left); System.out.print(root.data + " "); inOrder(root.right); } } void postOrder(Node root) { if(root != null) { postOrder(root.left); postOrder(root.right); System.out.print(root.data + " "); } } public static void main (String[] args) { BinaryTree tree = new BinaryTree(); root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); ...

  Method 1:  Method 2 :  1.  Recursive Program 2. Iterative Program - Stack 3. Iterative Program - Morris 4. Level Order Traversal

 A binary tree of height "h" having maximum number of nodes is called full binary tree. When a binary tree is represented in an array and there is no blank spaces in the tree between the nodes then tree is called complete binary tree . Or, A complete binary tree of height h will be a full binary tree upto height (h-1). 1. A full binary tree is always a complete binary tree 2. To represent a tree in an array we should have complete binary tree else there will be empty spaces between elements. Strict binary tree has 0 or 2 nodes. Strict binary tree may or may not be complete binary tree.

 

A tree that can have maximum m child nodes is called m-ary tree. Strict m-ary tree : A tree must have all nodes with either 0 or m child nodes. Nodes vs Height of m-ary tree :  Internal Nodes vs External Nodes : Number of external nodes = (m-1) * internal nodes + 1

 A binary tree that has all nodes with exactly 0 or 2 child nodes is called strict binary tree. Height vs Nodes :  Internal Nodes vs External Nodes :  Number of external nodes = Number of internal nodes + 1

 Tree : Tree is collection of nodes and edges. Or, it's collection of nodes where one node is taken as root node and rest of the nodes are divided into disjoint subsets and each subset is tree or subtree.  Tree terminologies :  Level starts from 1 onwards (we count nodes) and height starts from 0 onwards (we counts edges).  Binary Tree : A tree that can have 0, 1 or 2 sub trees, is called binary tree. How many binary trees can be generated from given number of nodes (n)? 1. Unlabelled Nodes : How many trees with maximum height? 2. Labelled Nodes :  Height vs Nodes Formula :  1. If height of binary tree is given? Minimum No. of Nodes (n) = h + 1 Maximum No. of Nodes (n) = 2^(n+1) - 1 2. If nodes of binary tree is given? Minimum Height (h) = log(n+1) - 1 Maximum  Height (h)  = n-1 Relationship b/w nodes with degree 0 and degree 2: Number of nodes with degree(0) = Number of nodes with degree(2) + 1