Level Order of Binary Tree Editorial

Practice Problem Link: Level Order Of Binary Tree

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a binary tree, return the level-order traversal of its elements.

Approach

The solution for this problem is to perform a single BFS and add the nodes to the answer array in the order they are encountered.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/

vector<int> getLevelOrderTraversal(Node* root) {
    queue<Node *> queue;
	queue.push(root);
	vector<int> traversal;
	while (!queue.empty()) {
		Node *currentElement = queue.front();
		queue.pop();
		traversal.push_back(currentElement->data);
		if(currentElement->left != NULL) {
			queue.push(currentElement->left);
		}
		if(currentElement->right != NULL) {
			queue.push(currentElement->right);
		}
	}	
	return traversal;
}

Java

/* This is the Node class definition

class Node {
	public Node left;
    public Node right;
    int data;

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	List<Integer> getLevelOrderTraversal(Node root) {
    	Queue<Node> queue = new LinkedList<Node>();
		queue.add(root);
		List<Integer> traversal = new ArrayList<>();
		while(!queue.isEmpty()) {
			Node currentElement = queue.poll();
			traversal.add(currentElement.data);
			if(currentElement.left != null) {
				queue.add(currentElement.left);
			}
			if(currentElement.right != null) {
				queue.add(currentElement.right);
			}
		}	
		return traversal;
	}
}