Binary Tree Preorder Traversal Inwards Coffee - Recursion In Addition To Iteration Example

Unlike a linked list too array which are linear information construction too tin alone live traversed linearly, at that spot are several ways to traverse a binary tree because of its hierarchical nature. The tree traversal algorithms are mainly divided into 2 types, the depth-first algorithms, too breadth-first algorithms. As their cite suggests, inward a depth-first algorithm, the tree is traversed downwards (towards the depth) before the adjacent sibling is visited, the PreOrder, InOrder and PostOrder traversal of a binary tree is genuinely depth-first traversal algorithms. On the breadth-first algorithm, too known every bit score club traversal, the entire breadth of the tree is traversed before moving to the adjacent level, therefore it is too known every bit score club traversal.

There are other algorithms to traverse a binary tree every bit good e.g. Monte Carlo tree search, which concentrates on analyzing the most promising moves, but the pre-order, post-order, too in-order traversal are the most pop ways to traverse a binary tree inward Java. They are too the most pop data construction too algorithm questions at beginner too intermediate level.

When y'all traverse a tree inward a depth-first way, y'all got 3 choices e.g. root, left subtree too correct subtree. Depending upon the club y'all see these three, dissimilar tree traversal algorithm is born.

In PreOrder traversal, the rootage is visited first, followed past times left subtree too the correct subtree, therefore it is too known every bit NLR (nod-left-right) algorithm every bit well.

For those, who don't know what is the important of traversing a binary tree? It's a procedure to see all nodes of a binary tree. It is too used to search a node inward the binary tree.

Btw, if y'all are novel to Computer Science too Data Structure, I too advise y'all bring together a comprehensive course of written report on Data construction too algorithms like Data Structures too Algorithms: Deep Dive Using Java course to larn to a greater extent than nigh a binary tree too diverse tree algorithms. They are extremely of import from the programming interview betoken of view.

Coming dorsum to the binary tree traversal algorithm, y'all tin implement the pre-order binary tree traversal algorithm inward Java either using recursion or iteration.

As I told y'all inward the article spell finding foliage nodes inward a binary tree, most of the tree based algorithms tin live easily implemented using recursion because a binary tree is a recursive information structure.

Though, I believe a programmer should too know how to solve a binary tree based employment amongst or without recursion to create good on coding interviews. Almost nine out of 10 times, Interviewer volition inquire y'all to solve the same employment using recursion too iteration every bit seen before amongst Fibonacci or reverse String problems.

In this article, I'll demonstrate y'all how to write a plan to traverse a binary tree using PreOrder traversal using both recursion too iteration inward Java.

How to traverse a Binary tree inward PreOrder inward Java using Recursion

Since binary tree is a recursive information construction (why? because after removing a node, residue of the construction is too a binary tree similar left too correct binary tree, similar to linked list, which is too a recursive information structure), it's naturally a goodness candidate for using recursive algorithm to solve tree based problem.

Steps on PreOrder traversal algorithm

1. visit the node
2. visit the left subtree
3. visit the correct subtree

You tin easily implement this pre-order traversal algorithm using recursion past times printing the value of the node too and then recursive calling the same preOrder() method amongst left subtree too correct subtree, every bit shown inward the next program:

private void preOrder(TreeNode node) {     if (node == null) {       return;     }     System.out.printf("%s ", node.data);     preOrder(node.left);     preOrder(node.right);   }

You tin encounter that it's simply a duet of employment of code. What is most of import hither is the base of operations case, from where the recursive algorithm starts to unwind. Here node == null is our base case because y'all receive got directly reached the foliage node too y'all cannot decease deeper now, it's fourth dimension to backtrack too decease to some other path.

The recursive algorithm is too really readable because y'all tin encounter that first, y'all impress the node value too then y'all are visiting the left subtree too lastly correct subtree. If y'all desire to larn to a greater extent than nigh binary tree information construction too recursive algorithms, I too advise joining Stack information structure. If y'all remember, recursion implicitly uses a Stack which started to unwind when your algorithm reaches the base of operations case.

You tin utilization external Stack to supervene upon that implicit stack too solve the employment without genuinely using recursion. This is too safer because directly your code volition non throw StackOverFlowError fifty-fifty for huge binary search trees but ofttimes they are non every bit concise too readable every bit their recursive counterpart.

 Anyway, hither is the preOrder algorithm without using recursion inward Java.

public void preOrderWithoutRecursion() {     Stack<TreeNode> nodes = new Stack<>();     nodes.push(root);      while (!nodes.isEmpty()) {       TreeNode electrical flow = nodes.pop();       System.out.printf("%s ", current.data);        if (current.right != null) {         nodes.push(current.right);       }       if (current.left != null) {         nodes.push(current.left);       }     }   }

To live honest, this is code is too slow to sympathise but at that spot is tricky role inward the middle of the algorithm, where y'all receive got to push correct sub-tree before the left subtree, which is dissimilar from the recursive algorithm. We initially force the rootage inward the Stack to start the traversal too and then utilization a spell loop to decease over Stack until its empty. In each iteration, nosotros pop chemical constituent for visiting it.

If y'all remember, Stack is a LIFO information structure, since nosotros desire to see the tree inward club of node-left-right, nosotros force correct node starting fourth dimension too left node afterward, so that inward the adjacent iteration when nosotros pop() from Stack nosotros acquire the left sub-tree.

This agency a binary tree is traversed inward the PreOrder traversal. If y'all modify the club of insertion into the stack, the tree volition live traversed inward the post-order traversal. See  Introduction to Algorithms past times Thomas S. Cormen to larn to a greater extent than nigh Stack information construction too its role inward converting recursive algorithm to an iterative one.

Here is a prissy diagram which shows pre-order traversal along amongst in-order too post-order traversal. Follow the blueish employment to traverse a binary tree inward pre-order.

Java Program to traverse a Binary tree inward PreOrder Algorithm

Here is our consummate plan to traverse a given binary tree inward PreOrder. In this program, y'all volition discovery an implementation of both recursive too iterative pre-order traversal algorithm. You tin run this plan from the command line or Eclipse IDE to examination too acquire a experience of how tree traversal works.

This plan has a course of written report called BinaryTree which represents a BinaryTree, hollo back it's non a binary search tree because TreeNode doesn't implement Comparable or Comparator interface. The TreeNode course of written report represents a node inward the binary tree, it contains a information role too 2 references to left too correct children.

I receive got created a preOrder() method inward the BinaryTree course of written report to traverse the tree inward pre-order. This is a public method but actual operate is done past times some other mortal method which is an overloaded version of this method.

The method accepts a TreeNode. Similarly, at that spot is some other method called preOrderWithoutRecursion() to implement the iterative pre-order traversal of the binary tree.

import java.util.Stack;  /*  * Java Program to traverse a binary tree using PreOrder traversal.   * In PreOrder the node value is printed first, followed past times see  * to left too correct subtree.   * input:  *     1  *    / \  *   2   five  *  / \   \  * 3   iv   half dozen  *   * output: 1 2 3 iv five half dozen   */ public class PreOrderTraversal {    public static void main(String[] args) throws Exception {      // build the binary tree given inward question     BinaryTree bt = new BinaryTree();     BinaryTree.TreeNode rootage = new BinaryTree.TreeNode("1");     bt.root = root;     bt.root.left = new BinaryTree.TreeNode("2");     bt.root.left.left = new BinaryTree.TreeNode("3");      bt.root.left.right = new BinaryTree.TreeNode("4");     bt.root.right = new BinaryTree.TreeNode("5");     bt.root.right.right = new BinaryTree.TreeNode("6");      // printing nodes inward recursive preOrder traversal algorithm     bt.preOrder();      System.out.println();      // traversing binary tree inward PreOrder without using recursion     bt.preOrderWithoutRecursion();    }  }  class BinaryTree {   static class TreeNode {     String data;     TreeNode left, right;      TreeNode(String value) {       this.data = value;       left = right = null;     }      boolean isLeaf() {       return left == null ? right == null : false;     }    }    // rootage of binary tree   TreeNode root;    /**    * Java method to impress tree nodes inward PreOrder traversal    */   public void preOrder() {     preOrder(root);   }    /**    * traverse the binary tree inward PreOrder    *     * @param node    *          - starting node, rootage    */   private void preOrder(TreeNode node) {     if (node == null) {       return;     }     System.out.printf("%s ", node.data);     preOrder(node.left);     preOrder(node.right);   }    /**    * Java method to see tree nodes inward PreOrder traversal without recursion.    */   public void preOrderWithoutRecursion() {     Stack<TreeNode> nodes = new Stack<>();     nodes.push(root);      while (!nodes.isEmpty()) {       TreeNode electrical flow = nodes.pop();       System.out.printf("%s ", current.data);        if (current.right != null) {         nodes.push(current.right);       }       if (current.left != null) {         nodes.push(current.left);       }     }   }  }  Output 1 2 3 iv five half dozen  1 2 3 iv five half dozen 

That's all about how to traverse a binary tree inward PreOrder inward Java. We'have seen how to implement a pre-order traversing algorithm using both recursion too iteration e.g. past times using a Stack information structure.

As a Computer Engineer or Programmer, y'all should know the basic tree traversal algorithms e.g. pre-order, inward club too postorder traversals. It becomes fifty-fifty to a greater extent than of import when y'all are preparing for coding interviews.

Anyway, simply hollo back that inward PreOrder traversal, node value is printed before visiting left too correct subtree. It's too a depth-first traversal algorithm too club of traversal is node-left-right, therefore it is too known NLR algorithm.

If y'all desire to meliorate this plan too exercise your Java science too then elbow grease to implement a binary tree using Generic so that y'all tin shop String or Integer every bit information into the binary tree. 

Further Learning
Data Structures too Algorithms: Deep Dive Using Java
solution)

5 Books to Learn Data Structure too Algorithms inward depth (books) 

How to impress all foliage nodes of a binary tree inward Java? (solution)

50+ Data Structure too Algorithms Problems from Interviews (list)

How to implement a recursive preorder algorithm inward Java? (solution)

Post club binary tree traversal without recursion (solution)

Recursive Post Order traversal Algorithm (solution)

How to impress foliage nodes of a binary tree without recursion? (solution)

Recursive InOrder traversal Algorithm (solution)

Iterative PreOrder traversal inward a binary tree (solution)

How to count the give away of foliage nodes inward a given binary tree inward Java? (solution)

100+ Data Structure Coding Problems from Interviews (questions)

75+ Coding Interview Questions for Programmers (questions)

10 Free Data Structure too Algorithm Courses for Programmers (courses)

Thanks for reading this coding interview inquiry so far. If y'all similar this String interview inquiry too then delight part amongst your friends too colleagues. If y'all receive got whatever inquiry or feedback too then delight drib a comment.

P. S. - If y'all are looking for some Free Algorithms courses to meliorate your agreement of Data Structure too Algorithms, too then y'all should too banking corporation gibe the Easy to Advanced Data Structures course of written report on Udemy. It's authored past times a Google Software Engineer too Algorithm proficient too its completely gratis of cost. 

Share this post