Tree - Inorder Traversal

Pratap SharmaMay 19th, 20214 mins read

This problem was asked in Hacker Rank.

Tree

If you'd like to checkout Tree: Preorder Traversal.

Problem

Given a function which has a parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values.

Write a function:

function inOrder(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 3 4 5 6

Sample input:

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

Output:

4 2 5 1 6 3 7 8

Write an efficient algorithm for the following assumptions

1 <= Nodes in the tree <= 500

Solution

Javascript Solution

let result = [];
function inOrderTraversal(node) {
  if (null == node) {
    return;
  }
  inOrderTraversal(node.left);
  result.push(node.data);
  inOrderTraversal(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 } } },
};

inOrderTraversal(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 inOrderTraversal(Node node){
         if(null == root){
            return;
        }

        inOrderTraversal(root.left);
        System.out.print(root.data + " ");
        inOrderTraversal(root.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.inOrderTraversal(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.