Pre-order Traversal of a Binary Tree

Given a Binary Tree, print the nodes of a binary tree in a pre-order fashion.


Video coming soon!



Subscribe for more updates


Algorithm/Insights

In the pre-order traversal for a given node 'n',
1. We first visit the node 'n' itself.
2. Then we traverse left-subtree of 'n' by calling printPreorder(n.left)
3. And finally we traverse right-subtree of 'n' by calling printPreorder(n.right)

Please check out the code section(printPreorder()) with visualization for illustration.


Algorithm Visualization




Code Snippet

			
package com.ideserve.nilesh.questions;

public class Tree {

	private TreeNode root;
	
	public TreeNode getRoot() {
		return root;
	}

	class TreeNode {
		
		private int data;
		private TreeNode left;
		private TreeNode right;
		
		public TreeNode(int data, TreeNode left, TreeNode right) {
			super();
			this.data = data;
			this.left = left;
			this.right = right;
		}

		public int getData() {
			return data;
		}

		public void setData(int data) {
			this.data = data;
		}

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

		public TreeNode() {
			super();
		}

		public TreeNode(int data) {
			super();
			this.data = data;
		}
		
		@Override
		public String toString() {
			return data+""; 
		}
	}

	public static void main(String[] args) {
		Tree tree = new Tree();
		tree.createSampleTree();
		tree.printPreorder();
	}

	/*
	 * Create a sample tree
	 * 				1
	 * 		2				3
	 * 4		5		6		7
	 * 
	 */
	public void createSampleTree() {
		root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3, new TreeNode(6), new TreeNode(7)));
	}

	/*
	 * Print preorder traversal
	 */
	public void printPreorder() {
		printPreorder(root);
	}
	
	private void printPreorder(TreeNode root) {
		if(root == null) {
			return;
		}
		System.out.print(root.getData() + " ");
		printPreorder(root.getLeft());
		printPreorder(root.getRight());
	}
}
		

Order of the Algorithm

Time Complexity is O((n))
Space Complexity is O((1))


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.


    Nilesh More