Trees Archives - Liesbeek

Lowest common ancestor of a binary tree

November 18, 2016 liesbeek Leave a comment

Here we are finding the lowest common ancestor of a binary tree. Here if the root2 is in between data 1 and data2 then we found
out ancestor.

package tree;


public class LowestCommonAncestorBinaryTree {
	
	static TreeNode root;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[] = {10,-10,30,8,6,9,25,60,28,78};
		
		for(int i=0; i<arr.length;i++)
		{
			insertInBST(arr[i]);

		}
		
		printBST(root);		
		
		TreeNode data1 = new TreeNode(28);
		TreeNode data2 = new TreeNode(78);
		TreeNode result = new TreeNode(1);
		result = lowestCommonAncestorBT(root, data1, data2);
		System.out.println("The result "+result.data);

	}
	

	/*
	 *  Here we are finding the lowest common ancestor of a binary tree. Here if the root2 is in between data 1 and data2 then we found 
	 *  out ancestor.
	 */
	private static TreeNode lowestCommonAncestorBT(TreeNode root2, TreeNode data1, TreeNode data2) {
		if(root2 == null)
		{
			return null;
		}
		
		if(root2.data == data1.data || root2.data == data2.data)
		{
			return root2;
		}
		
		TreeNode left = lowestCommonAncestorBT(root2.left, data1, data2);
		TreeNode right = lowestCommonAncestorBT(root2.right, data1, data2);
		
		if(left != null && right != null)
		{
			return root2;
		}
		
		if(left == null && right == null)
		{
			return null;
		}
		
		return left != null ? left : right;
				
	}


	// Here we are printing the data from the root
	private static void printBST(TreeNode root2) {
		if(root2 != null)
		{
			printBST(root2.left);
			System.out.println(root2.data);
			printBST(root2.right);
		}
	}
	
	// Here we are inserting the data in the tree node
	private static void insertInBST(int data) {
		TreeNode newNode = new TreeNode(data);
		
		if(root == null)
		{
			root = newNode;
			return;
		}
		
		TreeNode current = root;
		TreeNode parent = null;
		
		while(true)
		{
			parent = current;
			if(data < current.data)
			{
				current = current.left;
				if(current == null)
				{
					parent.left = newNode;
					return;
				}
			} else {
				current = current.right;
				if(current == null)
				{
					parent.right = newNode;
					return;
				}
			}
		}
	}

}

100

101

102

103

104

105

106

package tree;

public class LowestCommonAncestorBinaryTree {

static TreeNode root;

public static void main(String[] args) {

// TODO Auto-generated method stub

int arr[] = {10,-10,30,8,6,9,25,60,28,78};

for(int i=0; i<arr.length;i++)

{

insertInBST(arr[i]);

}

printBST(root);

TreeNode data1 = new TreeNode(28);

TreeNode data2 = new TreeNode(78);

TreeNode result = new TreeNode(1);

result = lowestCommonAncestorBT(root, data1, data2);

System.out.println("The result "+result.data);

}

* Here we are finding the lowest common ancestor of a binary tree. Here if the root2 is in between data 1 and data2 then we found

* out ancestor.

private static TreeNode lowestCommonAncestorBT(TreeNode root2, TreeNode data1, TreeNode data2) {

if(root2 == null)

{

return null;

}

if(root2.data == data1.data || root2.data == data2.data)

{

return root2;

}

TreeNode left = lowestCommonAncestorBT(root2.left, data1, data2);

TreeNode right = lowestCommonAncestorBT(root2.right, data1, data2);

if(left != null && right != null)

{

return root2;

}

if(left == null && right == null)

{

return null;

}

return left != null ? left : right;

}

// Here we are printing the data from the root

private static void printBST(TreeNode root2) {

if(root2 != null)

{

printBST(root2.left);

System.out.println(root2.data);

printBST(root2.right);

}

// Here we are inserting the data in the tree node

private static void insertInBST(int data) {

TreeNode newNode = new TreeNode(data);

if(root == null)

{

root = newNode;

return;

}

TreeNode current = root;

TreeNode parent = null;

while(true)

{

parent = current;

if(data < current.data)

{

current = current.left;

if(current == null)

{

parent.left = newNode;

return;

}

} else {

current = current.right;

if(current == null)

{

parent.right = newNode;

return;

}

Result: 30

Lowest Common Ancestor of a Binary Search Tree

November 12, 2016 liesbeek Leave a comment

Today we are finding the lowest common ancestor of a binary search tree. Here if the root data is in between data 1 and data 2 then we found out our lowest common ancestor.

Below is the code:

package tree;


public class LowestCommonAncestorBST {
	
	static TreeNode root;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[] = {10,-10,30,8,6,9,25,60,28,78};
		
		for(int i=0; i<arr.length;i++)
		{
			insertInBST(arr[i]);

		}
		
		printBST(root);		
		lowestCommonAncestorBST(root, 28, 78);
		lowestCommonAncestorBST(root, 6, 9);
		lowestCommonAncestorBST(root, 30, 78);

	}
	

	/*
	 *  Here we are finding the lowest common ancestor of a binary search tree. Here if the root2 is in between data 1 and data2 then we found 
	 *  out ancestor.
	 */
	private static void lowestCommonAncestorBST(TreeNode root2, int data1, int data2) {
		if(root2 == null)
		{
			return;
		}
		
		if(root2.data > Math.max(data1, data2))
		{
			lowestCommonAncestorBST(root2.left, data1, data2);
		} else if(root2.data < Math.min(data1, data2))
		{
			lowestCommonAncestorBST(root2.right, data1, data2);
		} else {
			System.out.println("The common ancestor is " +root2.data);
		}
	}


	// Here we are printing the data from the root
	private static void printBST(TreeNode root2) {
		if(root2 != null)
		{
			printBST(root2.left);
			System.out.println(root2.data);
			printBST(root2.right);
		}
	}
	
	// Here we are inserting the data in the tree node
	private static void insertInBST(int data) {
		TreeNode newNode = new TreeNode(data);
		
		if(root == null)
		{
			root = newNode;
			return;
		}
		
		TreeNode current = root;
		TreeNode parent = null;
		
		while(true)
		{
			parent = current;
			if(data < current.data)
			{
				current = current.left;
				if(current == null)
				{
					parent.left = newNode;
					return;
				}
			} else {
				current = current.right;
				if(current == null)
				{
					parent.right = newNode;
					return;
				}
			}
		}
	}

}

package tree;

public class LowestCommonAncestorBST {

static TreeNode root;

public static void main(String[] args) {

// TODO Auto-generated method stub

int arr[] = {10,-10,30,8,6,9,25,60,28,78};

for(int i=0; i<arr.length;i++)

{

insertInBST(arr[i]);

}

printBST(root);

lowestCommonAncestorBST(root, 28, 78);

lowestCommonAncestorBST(root, 6, 9);

lowestCommonAncestorBST(root, 30, 78);

}

* Here we are finding the lowest common ancestor of a binary search tree. Here if the root2 is in between data 1 and data2 then we found

* out ancestor.

private static void lowestCommonAncestorBST(TreeNode root2, int data1, int data2) {

if(root2 == null)

{

return;

}

if(root2.data > Math.max(data1, data2))

{

lowestCommonAncestorBST(root2.left, data1, data2);

} else if(root2.data < Math.min(data1, data2))

{

lowestCommonAncestorBST(root2.right, data1, data2);

} else {

System.out.println("The common ancestor is " +root2.data);

}

// Here we are printing the data from the root

private static void printBST(TreeNode root2) {

if(root2 != null)

{

printBST(root2.left);

System.out.println(root2.data);

printBST(root2.right);

}

// Here we are inserting the data in the tree node

private static void insertInBST(int data) {

TreeNode newNode = new TreeNode(data);

if(root == null)

{

root = newNode;

return;

}

TreeNode current = root;

TreeNode parent = null;

while(true)

{

parent = current;

if(data < current.data)

{

current = current.left;

if(current == null)

{

parent.left = newNode;

return;

}

} else {

current = current.right;

if(current == null)

{

parent.right = newNode;

return;

}

package tree;

public class TreeNode {
	int data;
	TreeNode left;
	TreeNode right;
	
	public TreeNode(int data) {
		this.data = data;
		this.left = null;
		this.right = null;
	}
}

package tree;

public class TreeNode {

int data;

TreeNode left;

TreeNode right;

public TreeNode(int data) {

this.data = data;

this.left = null;

this.right = null;

}

Output:
The common ancestor is 30
The common ancestor is 8
The common ancestor is 30

Spiral Order In BinaryTree

November 11, 2016 liesbeek Leave a comment

Today we will cover Tree Traversal Spiral Order topic. We are using 2 stack in this. First we push value in stack 1 and then it’s child in stack 2. Then doing the same steps till every node is covered.

Below is the running code:

package tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class SpiralOrderInBinaryTree {
	
	static TreeNode root;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[] = {10,5,6,8,7,4};
		
		for(int i=0; i<arr.length;i++)
		{
			insertInBST(arr[i]);

		}
		
		printBST(root);		
		System.out.println("---------------Spiral Order In BinaryTree Printing-------------");
		spiralOrder(root);
	}
	
	/*
	 *  Here we are using 2 stack. First we push value in stack 1 and then it's child in stack 2. Then doing the same steps till every node is covered.
	 */
	private static void spiralOrder(TreeNode root2) {
		if(root2 == null)
		{
			return;
		}
		
		Stack<TreeNode> s1 = new Stack<TreeNode>();
		Stack<TreeNode> s2 = new Stack<TreeNode>();
		s1.push(root2);
		
		while(!s1.isEmpty() || !s2.isEmpty())
		{
			while(!s1.isEmpty())
			{
				root2 = s1.pop();
				System.out.println(root2.data);
				if(root2.right != null)
				{
					s2.push(root2.right);
				}
				if(root2.left != null)
				{
					s2.push(root2.left);
				}
			
			}
			
			while(!s2.isEmpty())
			{
				root2 = s2.pop();
				System.out.println(root2.data);
				if(root2.left != null)
				{
					s1.push(root2.left);
				}
				if(root2.right != null)
				{
					s1.push(root2.right);
				}
				
			}
		}
	}

	// Here we are printing the data from the root
	private static void printBST(TreeNode root2) {
		if(root2 != null)
		{
			printBST(root2.left);
			System.out.println(root2.data);
			printBST(root2.right);
		}
	}
	
	// Here we are inserting the data in the tree node
	private static void insertInBST(int data) {
		TreeNode newNode = new TreeNode(data);
		
		if(root == null)
		{
			root = newNode;
			return;
		}
		
		TreeNode current = root;
		TreeNode parent = null;
		
		while(true)
		{
			parent = current;
			if(data < current.data)
			{
				current = current.left;
				if(current == null)
				{
					parent.left = newNode;
					return;
				}
			} else {
				current = current.right;
				if(current == null)
				{
					parent.right = newNode;
					return;
				}
			}
		}
	}

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

package tree;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

public class SpiralOrderInBinaryTree {

static TreeNode root;

public static void main(String[] args) {

// TODO Auto-generated method stub

int arr[] = {10,5,6,8,7,4};

for(int i=0; i<arr.length;i++)

{

insertInBST(arr[i]);

}

printBST(root);

System.out.println("---------------Spiral Order In BinaryTree Printing-------------");

spiralOrder(root);

}

* Here we are using 2 stack. First we push value in stack 1 and then it's child in stack 2. Then doing the same steps till every node is covered.

private static void spiralOrder(TreeNode root2) {

if(root2 == null)

{

return;

}

Stack<TreeNode> s1 = new Stack<TreeNode>();

Stack<TreeNode> s2 = new Stack<TreeNode>();

s1.push(root2);

while(!s1.isEmpty() || !s2.isEmpty())

{

while(!s1.isEmpty())

{

root2 = s1.pop();

System.out.println(root2.data);

if(root2.right != null)

{

s2.push(root2.right);

}

if(root2.left != null)

{

s2.push(root2.left);

}

while(!s2.isEmpty())

{

root2 = s2.pop();

System.out.println(root2.data);

if(root2.left != null)

{

s1.push(root2.left);

}

if(root2.right != null)

{

s1.push(root2.right);

}

// Here we are printing the data from the root

private static void printBST(TreeNode root2) {

if(root2 != null)

{

printBST(root2.left);

System.out.println(root2.data);

printBST(root2.right);

}

// Here we are inserting the data in the tree node

private static void insertInBST(int data) {

TreeNode newNode = new TreeNode(data);

if(root == null)

{

root = newNode;

return;

}

TreeNode current = root;

TreeNode parent = null;

while(true)

{

parent = current;

if(data < current.data)

{

current = current.left;

if(current == null)

{

parent.left = newNode;

return;

}

} else {

current = current.right;

if(current == null)

{

parent.right = newNode;

return;

}

TreeNode.java

package tree;

public class TreeNode {
	int data;
	TreeNode left;
	TreeNode right;
	
	public TreeNode(int data) {
		this.data = data;
		this.left = null;
		this.right = null;
	}
}

package tree;

public class TreeNode {

int data;

TreeNode left;

TreeNode right;

public TreeNode(int data) {

this.data = data;

this.left = null;

this.right = null;

}

Output:

4
5
6
7
8
10
—————Spiral Order In BinaryTree Printing————-
10
5
6
4
8
7

Category: Trees

Lowest common ancestor of a binary tree

Lowest Common Ancestor of a Binary Search Tree

Spiral Order In BinaryTree

Recent Posts

Get Latest Interview questions