Basics of Tree Data Structure
Tags: dsa, beginners, backend, algorithms
Published: 2023-05-25 04:15:28

## Basic's of TREE

**Pre-Order iterative : (Root , left , right)**


_You have the root (print it), check for right node first (add it into the stack) and check for left node (add it into stack). 
Pop the stack (print it), continue the loop till stack is empty_.

static ArrayList < Integer > preOrderTrav(Node curr) {
    ArrayList < Integer > preOrder = new ArrayList < Integer > ();
        if (curr == null)
            return preOrder;
        Stack < Node > s = new Stack < > ();
        s.push(curr);
        while (!s.isEmpty()) {
            Node topNode = s.peek();
            preOrder.add(topNode.data);
            s.pop();
            if (topNode.right != null)
                s.push(topNode.right);
            if (topNode.left != null)
                s.push(topNode.left);
        }
        return preOrder;
    }





**In-Order Iterative : (Left , Root , Right)**

_Iterate all the left nodes of the tree (while adding all the left nodes into Stack) and at the end of left node (print the left node), pop the stack (root of last node) print it and look for right node if present (print it).
 Continue the loop for infinity break if stack is empty._

 
 static ArrayList < Integer > inOrderTrav(Node curr) {
        ArrayList < Integer > inOrder = new ArrayList < > ();
        Stack < Node > s = new Stack < > ();
        while (true) {
            if (curr != null) {
                s.push(curr);
                curr = curr.left;
            } else {
                if (s.isEmpty()) break;
                curr = s.peek();
                inOrder.add(curr.data);
                s.pop();
                curr = curr.right;
            }
        }
        return inOrder;
    }






** Post-Order Iterative: (Left , Right , Root)**

 

**Approach 1 :using one stack**

_Print the value if both left and right value is null, and if the tree has only right nodes then check for (temp == st.peek().right) because to skip the duplication of iteration._

 static ArrayList < Integer > postOrderTrav(Node cur) {

        ArrayList < Integer > postOrder = new ArrayList < > ();
        if (cur == null) return postOrder;

        Stack < Node > st = new Stack < > ();
        while (cur != null || !st.isEmpty()) {

            if (cur != null) {
                st.push(cur);
                cur = cur.left;
            } else {
                Node temp = st.peek().right;
                if (temp == null) {
                    temp = st.peek();
                    st.pop();
                    postOrder.add(temp.data);
                    while (!st.isEmpty() && temp == st.peek().right) {
                        temp = st.peek();
                        st.pop();
                        postOrder.add(temp.data);
                    }
                } else cur = temp;
            }
        }
        return postOrder;


    }


**Approach 2: (using 2 stacks)**

_As Stack2 is used to store the root
Stack1 will store first right nodes first and left nodes
Popping the stack1 and adding the root into stack2_


static ArrayList < Integer > postOrderTrav(Node curr) {

        ArrayList < Integer > postOrder = new ArrayList < > ();
        if (curr == null) return postOrder;

        Stack < Node > s1 = new Stack < > ();
        Stack < Node > s2 = new Stack < > ();
        s1.push(curr);
        while (!s1.isEmpty()) {
            curr = s1.peek();
            s1.pop();
            s2.push(curr);
            if (curr.left != null)
                s1.push(curr.left);
            if (curr.right != null)
                s1.push(curr.right);
        }
        while (!s2.isEmpty()) {
            postOrder.add(s2.peek().data);
            s2.pop();
        }
        return postOrder;
    }