Saturday 26 August 2023

InOrder Traversal in BinaryTree using iterative method and Stack(Code in Java)


import java.util.*;


public class test {

    static class Node {

        int data;

        Node left;

        Node right;


        public Node(int data) {

            this.data = data;

            this.left = null;

            this.right = null;

        }

    }


    static class BinaryTree {

        static Node buildTree(Scanner scanner, String position, int parentValue) {

            System.out.print("Add " + position + " node for " + parentValue + " (y/n): ");

            String userChoice = scanner.next();


            if (userChoice.equalsIgnoreCase("y")) {

                System.out.print("Enter " + position + " node value: ");

                int nodeValue = scanner.nextInt();

                Node newNode = new Node(nodeValue);


                newNode.left = buildTree(scanner, "left", nodeValue);

                newNode.right = buildTree(scanner, "right", nodeValue);


                return newNode;

            } else {

                return null;

            }

        }

    }

    //levelorder traversal

    public static void levelorder(Node root)

    {

        if(root==null) return;

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

        q.add(root);

        q.add(null);

        while(!q.isEmpty())

        {

            Node currnode = q.remove();

            if(currnode==null) //NULL DENOTES NEW LINE

            {

                System.out.println();

                if(q.isEmpty())

                {

                    break;

                }

                else

                {

                    q.add(null);

                }

            }

            else

            {

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

                if(currnode.left!=null)

                {

                    q.add(currnode.left);

                }

                if(currnode.right!=null)

                {

                    q.add(currnode.right);

                }

            }

        }

    }


    public static ArrayList<Integer> preorderUsingStack(Node root)

    {

        ArrayList<Integer> preorderArrayList = new ArrayList<Integer>();

        if (root==null) return preorderArrayList;

        Stack<Node> st = new Stack<Node>();

        st.push(root);

        while(!st.isEmpty())

        {

            root = st.pop();

            preorderArrayList.add(root.data);

            if(root.right != null)

            {

                st.push(root.right);

            }

            if(root.left != null)

            {

                st.push(root.left);

            }


        }

        return preorderArrayList;

    }


    public static ArrayList<Integer> inorderUsingStack(Node root)

    {

        ArrayList<Integer> inorderArrayList = new ArrayList<Integer>();

        if (root == null) return null;

        Stack<Node> st = new Stack<Node>();

        Node node = root;

        while(true)

        {

            if(node != null)

            {

                st.push(node);

                node = node.left;

            }

            else

            {

                if(st.isEmpty())

                {

                    break;

                }

                node = st.pop();

                inorderArrayList.add(node.data);

                node = node.right;

            }

        }

        return inorderArrayList;

    }


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        BinaryTree bt = new BinaryTree();

        

        System.out.print("Enter root node value: ");

        int rootValue = scanner.nextInt();

        Node root = new Node(rootValue);


        root.left = bt.buildTree(scanner, "left", rootValue);

        root.right = bt.buildTree(scanner, "right", rootValue);


        System.out.println("Tree construction complete.");

        levelorder(root);

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

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

        scanner.close();

    }

}



  



No comments:

Post a Comment

Good thoughtful question on Binary search on answers

Problem link:  https://leetcode.com/problems/maximize-score-of-numbers-in-ranges/description/ Solution: //import java.util.Arrays; class So...