Scribd
Upload
5 views6 pages

Linked List

The document contains a Java program that implements a binary search tree with various functionalities such as adding nodes, calculating height, depth, diameter, and finding ancestors. It also includes methods for tree traversals: inorder, preorder, postorder, and level order. The main method demonstrates these functionalities using a predefined array of integers.

Uploaded by

rohithkumarcbaalraj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views6 pages

Linked List

The document contains a Java program that implements a binary search tree with various functionalities such as adding nodes, calculating height, depth, diameter, and finding ancestors. It also includes methods for tree traversals: inorder, preorder, postorder, and level order. The main method demonstrates these functionalities using a predefined array of integers.

Uploaded by

rohithkumarcbaalraj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 6

import java.util.

*;

public class Main

static class Node{

int data;

Node left;

Node right;

Node(int data){

this.data=data;

this.left=null;

this.right=null;

static Node root;

public static Node add(Node root,int data){

if(root==null){

return new Node(data);

if(data>root.data){

root.right=add(root.right,data);

else if(data<root.data){

root.left=add(root.left,data);

return root;

public static int height(Node root){

if(root==null){
return 0;

int lh=height(root.left);

int rh=height(root.right);

return 1 + Math.max(rh,lh);

public static int depth(Node root,int val){

if(root==null){

return -1;

if(root.data==val){

return 0;

int ld=depth(root.left,val);

int rd=depth(root.right,val);

if(ld!=-1){

return ld+1;

if(rd!=-1){

return rd+1;

return -1;

static int max=0;

public static int diameter(Node root){

if(root==null){

return 0;

}
int ldia=diameter(root.left);

int rdia=diameter(root.right);

max=Math.max(max,ldia+rdia);

return 1+Math.max(ldia,rdia);

public static int ancestor(Node root,int p,int q){

if(root==null){

return 0;

if(p<root.data && q<root.data){

return ancestor(root.left,p,q);

else if(p>root.data && q>root.data){

return ancestor(root.right,p,q);

else{

return root.data;

public static void inorder(Node root){

if(root==null){

return;

inorder(root.left);

System.out.print(root.data+" ");

inorder(root.right);

public static void postorder(Node root){


if(root==null){

return;

postorder(root.left);

postorder(root.right);

System.out.print(root.data+" ");

public static void preorder(Node root){

if(root==null){

return;

System.out.print(root.data+" ");

preorder(root.left);

preorder(root.right);

public static List<List<Integer>> levelorder(Node root){

List<List<Integer>> result=new ArrayList<>();

if(root==null){

return result;

Queue<Node> q=new LinkedList<>();

q.add(root);

while(!q.isEmpty()){

int len=q.size();

List<Integer> list=new ArrayList<>();

for(int i=0;i<len;i++){

Node curr=q.poll();

list.add(curr.data);
if(curr.left!=null) q.add(curr.left);

if(curr.right!=null) q.add(curr.right);

result.add(list);

return result;

public static void main(String[] args) {

int[] arr = {20,10,30,7,11,6,8,4,9,21,31,28,29};

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

root=add(root,arr[i]);

System.out.println(height(root));

System.out.println(depth(root,7));

max=0;

diameter(root);

System.out.println(max);

int p=7,q=9;

System.out.println(ancestor(root,p,q));

inorder(root);

System.out.println();

preorder(root);

System.out.println();

postorder(root);

System.out.println();

List<List<Integer>> output=levelorder(root);

for(List<Integer> lev:output){

for(int i:lev){
System.out.print(i+" ");

System.out.println();

You might also like