DSA Day 82/100

Topic: Tree

1) Iterative Inorder Traversal	Easy
2) Level Order Traversal	Easy
3) Height of Binary Tree	Easy

Iterative Inorder Traversal

Input:
       1
     /  \
    3    2
Output: 3 1 2

class Node {
    int data;
    Node left, right;
   Node(int item)    {
        data = item;
        left = right = null;
    }
}
class Solution {
    ArrayList<Integer> inOrder(Node root) {

        ArrayList<Integer> al = new ArrayList<Integer>();
        if(root==null)
        {return al;}

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



        while(root!=null || !st.isEmpty()){

            if(root!=null){
                st.push(root);
                root = root.left;
            }

            else{
                root = st.pop();
                al.add(root.data);
                root = root.right;
            }
        }

        return al;
    }
}

Level Order Traversal

Input:
    1
  /   \ 
 3     2
Output:1 3 2

class Node
{
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
}
class Solution
{
    static ArrayList <Integer> levelOrder(Node node) 
    {
        Queue<Node> q = new ArrayDeque<Node>();
        ArrayList<Integer> al = new ArrayList<Integer>();


        q.add(node);


        while(!q.isEmpty()){
            node  = q.remove();
            al.add(node.data);
            if(node.left!=null){
                q.add(node.left);
            }
            if(node.right!=null){
                q.add(node.right);
            }
        }
        return al;

    }
}

Height of Binary Tree

Input:
  2
   \
    1
   /
 3
Output: 3

class Node
{
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class Solution {
    int height(Node node) 
    {
        if(node==null){
            return 0;
        }
        else{
            return Math.max(height(node.left),height(node.right))+1;
        }
    }
}

Thankyou for reading :)