Program Two Nodes of a BST are Swapped correct the BST

June 23, 2019

Please write your own version of program in the comment section below in different languages. Best answer will be uploaded on the website page once, the page is ready

One comment on “Program Two Nodes of a BST are Swapped correct the BST”


  • Zubair

    package com.company;

    import java.io.*;
    import java.lang.*;
    import java.util.*;

    public class Main {
    public static void main(String[] args) {
    abc tree =new abc();
    node root =new node(6);
    root.left=new node(9);
    root.right=new node(3);
    root.left.left=new node(1);
    root.left.right=new node(4);
    root.right.right=new node(13);
    tree.inorder(root);
    tree.restorebst(root);
    System.out.println();
    tree.inorder(root);

    }
    }
    class node {
    int data;
    node left;
    node right;

    public node(int value) {
    this.data = value;
    this.left=null;
    this.right=null;
    }
    }
    class abc{
    public node root=null;
    node first ,mid,last ,prev;
    public void restorebst(node node){
    first=mid=last=prev=null;
    calculate(node);
    if (first!=null&&last!=null){
    int temp = first.data;
    first.data= last.data;
    last.data=temp;
    }
    else if (first!=null&&mid!=null){
    int temp = first.data;
    first.data = mid.data;
    mid.data = temp;
    }
    }
    public void calculate(node node){
    if (node==null){
    return;
    }
    calculate(node.left);
    if (prev!=null&&node.data< prev.data){
    if (first==null){
    first=prev;
    mid=node;
    }
    else {
    last=node;
    mid =null;
    }
    }
    prev=node;
    calculate(node.right);
    }
    public void inorder(node node ){
    if (node==null){
    return;
    }
    inorder(node.left);
    System.out.print(node.data+" ");
    inorder(node.right);
    }
    }