Basics of Tree Data Structure

Shambuling patil — Thu, 25 May 2023 04:15:28 +0000

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;
}

DEV Community: Shambuling patil

Basics of Tree Data Structure

Basic's of TREE