Tree - Preorder Traversal

Pratap SharmaMay 30th, 20204 mins read

This problem was asked in Hacker Rank.

Problem

Complete the preOrder function in your editor below, which has parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values.

Write a function:

function preOrder(node);

that, given a pointer of root node and must print the values as a single line os space-separated values.

Examples

Sample input:

Output:

1 2 5 3 4 6

Sample input:

      1
    /   \
   2     3
  / \   / \
 4   5 6   7
            \
             8

Output:

1 2 4 5 3 6 7 8

Write an efficient algorithm for the following assumptions

1 <= Nodes in the tree <= 500

Solution

Javascript Solution

let result = [];
function preOrderTraversal(node) {
  if (null == node) {
    return;
  }
  result.push(node.data);
  preOrderTraversal(node.left);
  preOrderTraversal(node.right);
}
let root = {
  data: 1,
  left: { data: 2, left: { data: 4 }, right: { data: 5 } },
  right: { data: 3, left: { data: 6 }, right: { data: 7, right: { data: 8 } } },
};

preOrderTraversal(root);
console.log(...result);

Java Solution

package com.pratap.sample.test;

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int data;
    Node left, right;

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

public class BinaryTree {

void preOrderTraversal(Node node){
        if(null == node){
            return;
        }
        System.out.println(" " + node.data);
        preOrderTraversal(node.left);
        preOrderTraversal(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.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        tree.root.right.left.right = new Node(8);

        tree.preOrderTraversal(tree.root);

    }
}

Result

I have passed all the test cases.

💌 If you’d like to receive more coding solutions in your inbox, you can sign up for the newsletter here.