In PreOrder traversal, the nodes are recursively visited in this order: Root, Left, Right. This traversal method is useful when you need to create a copy of the tree.

Java Implementation:

Below is a Java example demonstrating PreOrder traversal on a binary tree.


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

class BinaryTree {
    Node root;
    void preOrder(Node node) {
        if (node == null)
            return;
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
    
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.preOrder(tree.root);
    }
}

Console Output:

1 2 4 5 3

N-ary Tree PreOrder Traversal

N-ary Tree Concept:

In an N-ary tree, each node can have more than two children. The PreOrder traversal for an N-ary tree involves visiting the root node first, followed by recursively visiting each child from left to right.

Java Implementation:

Below is an example of PreOrder traversal on an N-ary tree.


import java.util.ArrayList;
import java.util.List;

class NaryNode {
    int data;
    List children;
    public NaryNode(int item) {
        data = item;
        children = new ArrayList<>();
    }
}

class NaryTree {
    NaryNode root;
    void preOrder(NaryNode node) {
        if (node == null)
            return;
        System.out.print(node.data + " ");
        for (NaryNode child : node.children) {
            preOrder(child);
        }
    }
    
    public static void main(String[] args) {
        NaryTree tree = new NaryTree();
        tree.root = new NaryNode(1);
        tree.root.children.add(new NaryNode(2));
        tree.root.children.add(new NaryNode(3));
        tree.root.children.get(0).children.add(new NaryNode(4));
        tree.root.children.get(0).children.add(new NaryNode(5));
        tree.preOrder(tree.root);
    }
}

Console Output:

1 2 4 5 3

Threaded Binary Tree PreOrder Traversal

Threaded Binary Tree Concept:

A threaded binary tree is a binary tree variant that makes use of null pointers to store in-order predecessor or successor information, reducing the need for stack or recursion during traversal.

Java Implementation:

The following example demonstrates PreOrder traversal in a threaded binary tree.


class ThreadedNode {
    int data;
    ThreadedNode left, right;
    boolean isThreaded;
    public ThreadedNode(int item) {
        data = item;
        left = right = null;
        isThreaded = false;
    }
}

class ThreadedBinaryTree {
    ThreadedNode root;
    void preOrder(ThreadedNode node) {
        while (node != null) {
            System.out.print(node.data + " ");
            if (node.left != null)
                node = node.left;
            else {
                while (node != null && node.isThreaded)
                    node = node.right;
                node = (node != null) ? node.right : null;
            }
        }
    }
    
    public static void main(String[] args) {
        ThreadedBinaryTree tree = new ThreadedBinaryTree();
        ThreadedNode n1 = new ThreadedNode(1);
        ThreadedNode n2 = new ThreadedNode(2);
        ThreadedNode n3 = new ThreadedNode(3);
        n1.left = n2;
        n1.right = n3;
        n2.isThreaded = true;
        n2.right = n1;
        tree.root = n1;
        tree.preOrder(tree.root);
    }
}

Console Output:

1 2 3

AVL Tree PreOrder Traversal

AVL Tree Concept:

An AVL tree is a self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one for all nodes.

Java Implementation:

This example shows how to perform a PreOrder traversal on an AVL tree.


class AVLNode {
    int data, height;
    AVLNode left, right;
    public AVLNode(int item) {
        data = item;
        height = 1;
    }
}

class AVLTree {
    AVLNode root;
    void preOrder(AVLNode node) {
        if (node == null)
            return;
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
    
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        tree.root = new AVLNode(10);
        tree.root.left = new AVLNode(5);
        tree.root.right = new AVLNode(20);
        tree.root.left.left = new AVLNode(3);
        tree.root.left.right = new AVLNode(7);
        tree.preOrder(tree.root);
    }
}

Console Output:

10 5 3 7 20

Red-Black Tree PreOrder Traversal

Red-Black Tree Concept:

A Red-Black tree is a balanced binary search tree with an extra bit of storage per node: its color, which can be either red or black. The tree maintains balance through rotations and color changes during insertions and deletions.

Java Implementation:

Here is how you can implement a PreOrder traversal on a Red-Black tree.


class RedBlackNode {
    int data;
    RedBlackNode left, right;
    boolean color; // true for red, false for black
    public RedBlackNode(int item) {
        data = item;
        left = right = null;
        color = true; // new nodes are red by default
    }
}

class RedBlackTree {
    RedBlackNode root;
    void preOrder(RedBlackNode node) {
        if (node == null)
            return;
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
    
    public static void main(String[] args) {
        RedBlackTree tree = new RedBlackTree();
        tree.root = new RedBlackNode(10);
        tree.root.left = new RedBlackNode(5);
        tree.root.right = new RedBlackNode(20);
        tree.root.left.left = new RedBlackNode(3);
        tree.root.left.right = new RedBlackNode(7);
        tree.preOrder(tree.root);
    }
}

Console Output:

10 5 3 7 20