Java Preorder Tree Traversal recursive and iterative flattening of tree

The Logic and Datastructure Essentials chapter of my book "Core Java Career Essentials" covered a lot of questiomns and answers on different data structures and where to use them with lots of diagrams and code snippets. This blog post covers just the  Preorder Tree Traversal with code snippets. The preorder tree structure is a very popular Java coding interview question:

The left nodes are traversed before the right nodes.

Q. How will you fltten a preorder tree in Java?
A.

Step 1: The TreeNode class can be decalred as shown below.

 
package com.mycompany.app14;

public class TreeNode
{
    private int value;
    private TreeNode left;
    private TreeNode right;
    
    public TreeNode(int value, TreeNode left, TreeNode right)
    {
        super();
        this.value = value;
        this.left = left;
        this.right = right;
    }
    
    public int getValue()
    {
        return value;
    }
    
    public void setValue(int value)
    {
        this.value = value;
    }
    
    public TreeNode getLeft()
    {
        return left;
    }
    
    public void setLeft(TreeNode left)
    {
        this.left = left;
    }
    
    public TreeNode getRight()
    {
        return right;
    }
    
    public void setRight(TreeNode right)
    {
        this.right = right;
    }
    
}

Step 2: Test class to construct the tree structure using the TreeNode class and traverse the tree bothe recursively and iteratively to printhe values in the Preorder.

 
package com.mycompany.app14;

import java.util.ArrayDeque;
import java.util.Deque;

public class Test
{
    public static void main(String[] args)
    {
        TreeNode root = createOneTo6PreOrderTree();
        printTreeRecursively(root);
        System.out.println("---------------------------------");
        printTreeIteratively(root);
    }
    
    private static TreeNode createOneTo6PreOrderTree()
    {
        TreeNode leaf3 = new TreeNode(3, null, null);
        TreeNode leaf4 = new TreeNode(4, null, null);
        TreeNode leaf6 = new TreeNode(6, null, null);
        
        TreeNode node5 = new TreeNode(5, leaf6, null);
        TreeNode node2 = new TreeNode(2, leaf3, leaf4);
        
        TreeNode root1 = new TreeNode(1, node2, node5);
        
        return root1;
    }
    
    /**
     * traverse the tree recursively and print
     * 
     * @param TreeNode node
     */
    private static void printTreeRecursively(TreeNode node)
    {
        //Exit condition for recursion 
        if (node == null)
        {
            return;
        }
        
        System.out.println(node.getValue());
        
        printTreeRecursively(node.getLeft());     //recurse left node 
        printTreeRecursively(node.getRight());    //recurse right node
        
    }
    
    /**
     * Achieved using a Deque (LIFO)
     * 
     * @param TreeNode node
     */
    private static void printTreeIteratively(TreeNode node)
    {
        Deque<TreeNode> s = new ArrayDeque<TreeNode>(6);
        s.push(node);  // push the root node
        
        while (!s.isEmpty())
        {
            node = s.pop();
            System.out.println(node.getValue());
            
            //stack is LIFO, so push the right node first
            if (node.getRight() != null)
            {
                s.push(node.getRight());
            }
            
            //stack is LIFO, so push the left node last
            if (node.getLeft() != null)
            {
                s.push(node.getLeft());
            }
        }
        
    }
}

Step 3: The iterative approach represented diagramatucally for better understanding. Shows how the numbers are pushed and popped.

Step 4: Output

 
1
2
3
4
5
6
---------------------------------
1
2
3
4
5
6

Related Posts by Categories