30 Days of Code

Day 23: BST Level-Order Traversal solution

Day 23: BST Level-Order Traversal – Hackerrank 30 Days Of Code Solution

Let’s solve Day 23: BST Level-Order Traversal. Level-order traversal, also known as breadth-first search, is a fundamental tree traversal algorithm that visits each level of a tree’s nodes from left to right, top to bottom. Join us on this exciting journey to explore level-order traversal and its practical application.😍

Task

A level-order traversal, also known as a breadth-first search, visits each level of a tree’s nodes from left to right, top to bottom. You are given a pointer, root, pointing to the root of a binary search tree. Complete the levelOrder function provided in your editor so that it prints the level-order traversal of the binary search tree.

Hint: You’ll find a queue helpful in completing this challenge.

Sample Input

6
3
5
4
7
2
1

Sample Output

3 2 5 1 4 7

Explanation

To solve this challenge, we need to implement the levelOrder function, which performs a level-order traversal of a given binary search tree. The level-order traversal visits each level of the tree’s nodes from left to right, top to bottom, and prints the node values in that order.

The levelOrder function should use a queue data structure to keep track of the nodes at each level. It starts by enqueuing the root node, and then iteratively dequeues a node, prints its value, and enqueues its left and right child nodes (if they exist).

Day 23: BST Level-Order Traversal Solution In Javascript

JavaScript
var queue = [root];
      while (queue.length > 0) {
        var node = queue.shift();
        write(node.data + " ");
        if(node.left) {
         queue.push(node.left);
        }
        if (node.right) {
         queue.push(node.right);
        }
      }
      function write(str){
        process.stdout.write(str);
      }

Day 23: BST Level-Order Traversal Solution In C++

C++
class Node {
public:
    int data;
    Node *left, *right;
    Node(int data) {
        this->data = data;
        left = right = nullptr;
    }
};

class BinarySearchTree {
public:
    Node *root;

    Node* insert(Node* root, int data) {
        if (root == nullptr) {
            root = new Node(data);
            return root;
        }

        if (data <= root->data) {
            if (root->left)
                insert(root->left, data);
            else
                root->left = new Node(data);
        } else {
            if (root->right)
                insert(root->right, data);
            else
                root->right = new Node(data);
        }

        return root;
    }

    void levelOrder(Node* root) {
        if (root == nullptr) return;

        queue<Node*> q;
        q.push(root);

        while (!q.empty()) {
            Node* node = q.front();
            q.pop();
            cout << node->data << " ";

            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }
    }
};

int main() {
    BinarySearchTree tree;
    tree.root = nullptr;

    int n, data;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> data;
        tree.root = tree.insert(tree.root, data);
    }

    tree.levelOrder(tree.root);
    return 0;
}

Day 23: BST Level-Order Traversal Solution In Java

Java
class Node {
    int data;
    Node left, right;

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

class BinarySearchTree {
    Node root;

    Node insert(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }

        if (data <= root.data) {
            if (root.left != null)
                insert(root.left, data);
            else
                root.left = new Node(data);
        } else {
            if (root.right != null)
                insert(root.right, data);
            else
                root.right = new Node(data);
        }

        return root;
    }

    void levelOrder(Node root) {
        if (root == null) return;

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.data + " ");

            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
    }
}

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        BinarySearchTree tree = new BinarySearchTree();
        tree.root = null;

        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            int data = scanner.nextInt();
            tree.root = tree.insert(tree.root, data);
        }

        tree.levelOrder(tree.root);
        scanner.close();
    }
}

Day 23: BST Level-Order Traversal Solution In Python

Python
def levelOrder(self, root):
        if root is None:
            return

        queue = [root]

        while queue:
            node = queue.pop(0)
            print(node.data, end=" ")

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

Day 23: BST Level-Order Traversal Solution In PHP

PHP
<?php

public function levelOrder($root){
    if($root == null) return;
    
    $queue = array($root);
    
    while(count($queue) > 0){
        $node = array_shift($queue);
        echo $node->data . " ";
        
        if($node->left != null) array_push($queue, $node->left);
        if($node->right != null) array_push($queue, $node->right);
    }
}

Learning from this Question

By solving the “Day 23: BST Level-Order Traversal” challenge, you can learn several important concepts:

  1. Level-order traversal: You will gain a deep understanding of the level-order traversal algorithm and its implementation.
  2. Breadth-first search: You will learn about breadth-first search, which is a fundamental graph traversal algorithm used in various applications.
  3. Binary Search Trees (BSTs): You will reinforce your knowledge of BSTs and their operations.
  4. Queue data structure: You will practice using the queue data structure, which is essential for implementing level-order traversal.
  5. Tree traversal algorithms: You will strengthen your understanding of different tree traversal algorithms and their applications.
  6. Problem-solving skills: You will enhance your problem-solving skills by designing and implementing a solution that meets the given requirements.

Conclusion

The “Day 23: BST Level-Order Traversal” challenge introduces the level-order traversal algorithm and its practical application in binary search trees. By implementing the levelOrder function, you will gain valuable experience in working with breadth-first search, queues, and tree traversal algorithms. The complete code for this challenge is available in my GitHub repository✨.

This exercise reinforces the importance of tree traversal algorithms in computer science and data structures, as they are essential for various applications, such as data processing, graph algorithms, and more⭐.

Don’t comment bad code – rewrite it

– Brian Kernighan

Day 22: Binary Search Trees – Hackerrank 30 Days Of Code Solution

Day 24: More Linked Lists – Hackerrank 30 Days Of Code Solution