Output order different

#1

why is my preorder traversal output coming different from the expected sample output?..Atleast I am sure that my code for creation of BST, deletion and pre-order traversal is correct

#2

@debprotim,
can you share your code as well?

#3

import java.util.*;
public class Main {
private class Node{
int data=0;
Node left;
Node right;

	Node()
	{
		this.data=0;
		this.left=null;
		this.right=null;
	}
}

private Node root;
private int size;

Main(){
	this.root=new Node();
}

public void constructBST(int[] arr)
{
	this.root=constructBST(arr,0,arr.length-1);
}
private Node constructBST(int[] arr,int lo,int hi)
{
	if(lo>hi)
	{
		return null;
	}
	int mid=(lo+hi)/2;
	Node nn=new Node();
	nn.data=arr[mid];

	nn.left=constructBST(arr,lo,mid-1);
	nn.right=constructBST(arr,mid+1,hi);

	return nn;
}


public void preorder()
{
	this.preorder(this.root);
}

private void preorder(Node root)
{
	if(root==null)
	{
		return;
	}		
	System.out.print(root.data+" ");
	preorder(root.left);
	preorder(root.right);
	
}

public void delete(int k)
{
	boolean ilc=false;
	this.delete(this.root,null,k,ilc);
}

private void delete(Node root,Node parent,int k,boolean ilc)
{
	if(k>root.data)
	{
		ilc=false;
		delete(root.right,root,k,ilc);
	}else if(k<root.data)
	{
		ilc=true;
		delete(root.left,root,k,ilc);
	}else{
		if(root.left==null && root.right==null)
		{
			if(ilc)
			{
				parent.left=null;
				return;
			}else{
				parent.right=null;
				return;
			}
		}else if(root.left!=null && root.right==null)
		{
			if(ilc)
			{
				parent.left=root.left;
				return;	
			}else{
				parent.right=root.left;
				return;
			}
		}else if(root.left==null && root.right!=null)
		{
			if(ilc)
			{
				parent.left=root.right;
				return;	
			}else{
				parent.right=root.right;
				return;
			}
		}else{
			int mx=max(root.left);
			root.data=mx;
			delete(root.left,root,mx,true);
		}
	}
}
public int max(Node root)
{
	while(root.right!=null)
	{
		root=root.right;
	}
	return root.data;
}
public static void main(String args[])throws Exception {
	Scanner sc=new Scanner(System.in);
	int t=sc.nextInt();
	while(t-->0)
	{
		int n=sc.nextInt();
		int[] arr=new int[n];
		for(int i=0;i<n;i++)
		{
			arr[i]=sc.nextInt();
		}
		for(int i=0;i<arr.length;i++)
		{
			for(int j=0;j<i;j++)
			{
				if(arr[j+1]<arr[j])
				{
					int temp=arr[j+1];
					arr[j+1]=arr[j];
					arr[j]=temp;
				}
			}
		} 
		Main tree=new Main();
		tree.constructBST(arr);
		n=sc.nextInt();
		for(int i=0;i<n;i++)
		{
			int ch=sc.nextInt();
			tree.delete(ch);
		}
		tree.preorder();
	}
}

}

#4

@debprotim,

Errors:

  1. a lot of cases were missing in the deletenode function when n1.left!=null &&n1.right==null and n1.left == null && n1.right != null.
  2. max function will be modified.
  3. Don’t sort the array before construction.

If the right child is not empty you need to find the inorder successor. What you are doing is correct, we can also replace it with inorder predecessor (max element on the left child node) but, the important thing to note is, inorder predecessor is needed only when right child is empty.

#5

@debprotim,
I have responded to you on chat.