A binary tree is a tree data structure in which every node has a maximum of two children, i.e., left and right. The left view of a binary tree is the list of nodes seen if the tree is looked at from the left side. It is the first node at each binary tree level from the root and going level by level. The left view is a significant binary tree traversal concept that can be applied to problems concerning the tree's structure.
This article will discuss the left view of binary tree, its algorithm, pseudo code, and example codes in C++, Java, and Python.
What is the Left View of Binary Tree?
The left view of a binary tree is the nodes when viewed from the left-hand side of the tree. It indicates that the leftmost node is in the left view at each tree level.
Example
1 1
/ \ /
2 3 --> 2
/ \ / \ / \
4 5 6 7 4 5
The left view of the binary tree will be: 1, 2, 4.
Explanation
- At level 0, node 1 is visible.
- At level 1, node 2 is visible.
- At level 2, node 4 is visible.
Methods to Implement List View of Binary Tree
Here are the methods to implement a list view of binary tree such as:
- Recursion
- Level Order Traversal
- Queue and Null Pointer
1. Using Recursion (DFS)
In the recursive method, we do a depth-first traversal of the tree and mark the level of each node. We consider only the first node visited at each level (the leftmost node) and append it to the left view.
Steps
- Do a DFS traversal of the tree.
- Maintain a variable maxLevel to keep track of the current maximum level reached.
- For every node, if its level exceeds maxLevel, add its value to the left view and update maxLevel.
- Visit the left child recursively, then the right child, so the leftmost node is visited first.
Pseudo Code
function leftView(root):
result = []
maxLevel = -1
function dfs(node, level):
if node is null:
return
if level > maxLevel:
result.append(node.value)
maxLevel = level
dfs(node.left, level + 1)
dfs(node.right, level + 1)
dfs(root, 0)
return result
C++
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
void dfs(Node* node, int level, int& maxLevel, vector<int>& result) {
if (node == nullptr) return;
if (level > maxLevel) {
result.push_back(node->data);
maxLevel = level;
}
dfs(node->left, level + 1, maxLevel, result);
dfs(node->right, level + 1, maxLevel, result);
}
vector<int> leftView(Node* root) {
vector<int> result;
int maxLevel = -1;
dfs(root, 0, maxLevel, result);
return result;
}
int main() {
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
vector<int> result = leftView(root);
for (int val : result) {
cout << val << " ";
}
return 0;
}
Java
import java.util.*;
class BinaryTree {
static class Node {
int data;
Node left, right;
Node(int val) {
data = val;
left = right = null;
}
}
static int maxLevel = -1;
public static void dfs(Node node, int level, List<Integer> result) {
if (node == null) return;
if (level > maxLevel) {
result.add(node.data);
maxLevel = level;
}
dfs(node.left, level + 1, result);
dfs(node.right, level + 1, result);
}
public static List<Integer> leftView(Node root) {
List<Integer> result = new ArrayList<>();
dfs(root, 0, result);
return result;
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
List<Integer> result = leftView(root);
for (int val : result) {
System.out.print(val + " ");
}
}
}
Python
import java.util.*;
class BinaryTree {
static class Node {
int data;
Node left, right;
Node(int val) {
data = val;
left = right = null;
}
}
static int maxLevel = -1;
public static void dfs(Node node, int level, List<Integer> result) {
if (node == null) return;
if (level > maxLevel) {
result.add(node.data);
maxLevel = level;
}
dfs(node.left, level + 1, result);
dfs(node.right, level + 1, result);
}
public static List<Integer> leftView(Node root) {
List<Integer> result = new ArrayList<>();
dfs(root, 0, result);
return result;
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
List<Integer> result = leftView(root);
for (int val : result) {
System.out.print(val + " ");
}
}
}
Explanation
- It is a recursive function that performs a depth-first traversal of the tree. It maintains the level of the present node and adds the first node it finds in each level to the result.
- It only adds the first node of each level to the result to ensure the left view.
- The operation starts by visiting the left subtree and the right subtree.
Output
1 2 4
2. Using Level Order Traversal (BFS)
Level order traversal or breadth-first search (BFS) visits all nodes at a level before proceeding to the next level. To get the left view, we can store the first node we see at every level.
Steps
- Use a queue to do tree traversal level by level.
- Consider the first node (leftmost node) for each level.
- Add every node's left and right child to proceed with the traversal.
Pseudo Code
function leftView(root):
if root is null:
return []
result = []
queue = []
queue.enqueue(root)
queue.enqueue(null) // Marker for end of level
while queue is not empty:
node = queue.dequeue()
if node is null:
if queue is not empty:
queue.enqueue(null) // Add marker for next level
else:
if queue.front() is null: // First node at this level
result.append(node.value)
if node.left:
queue.enqueue(node.left)
if node.right:
queue.enqueue(node.right)
return result
C++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
vector<int> leftView(Node* root) {
vector<int> result;
if (root == nullptr) return result;
queue<Node*> q;
q.push(root);
q.push(nullptr); // Marker for end of level
while (!q.empty()) {
Node* current = q.front();
q.pop();
if (current == nullptr) {
if (!q.empty()) q.push(nullptr); // Add marker for next level
} else {
if (q.front() == nullptr) { // First node at this level
result.push_back(current->data);
}
if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
}
return result;
}
int main() {
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
vector<int> result = leftView(root);
for (int val : result) {
cout << val << " ";
}
return 0;
}
Java
import java.util.*;
class BinaryTree {
static class Node {
int data;
Node left, right;
Node(int val) {
data = val;
left = right = null;
}
}
public static List<Integer> leftView(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<Node> q = new LinkedList<>();
q.add(root);
q.add(null); // Marker for end of level
while (!q.isEmpty()) {
Node current = q.poll();
if (current == null) {
if (!q.isEmpty()) q.add(null); // Add marker for next level
} else {
if (q.peek() == null) { // First node at this level
result.add(current.data);
}
if (current.left != null) q.add(current.left);
if (current.right != null) q.add(current.right);
}
}
return result;
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
List<Integer> result = leftView(root);
for (int val : result) {
System.out.print(val + " ");
}
}
}
Python
from collections import deque
class Node:
def __init__(self, val):
self.data = val
self.left = None
self.right = None
def left_view(root):
if root is None:
return []
result = []
queue = deque([root, None]) # Add marker for end of level
while queue:
node = queue.popleft()
if node is None:
if queue:
queue.append(None) # Add marker for next level
else:
if queue[0] is None: # First node at this level
result.append(node.data)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print(left_view(root))
Explanation
- This utilizes BFS with a queue to perform level by level traversal of the tree.
- A marker (None) to indicate the end of every level.
- The leftmost node in a level is the only node appended to the result, thereby giving the left view of the tree.
Output
[1, 2, 4]
3. Queue and Null Pointer
This method is a variation of level order traversal, and we use a unique marker (null pointer) to mark the end of a level. This permits us to locate the front node of every level without maintaining a count of the current level.
Steps
- Insert the root node and a null pointer as a marker at the end of the level in the queue.
- When we dequeue nodes, whenever we come across a null pointer, that implies we have one level done.
- The first node met upon finding each null pointer belongs to the left view.
- Push the right and left children of the nodes to visit the next level.
Pseudo Code
function leftView(root):
if root is null:
return []
result = []
queue = []
queue.enqueue(root)
queue.enqueue(null) // Marker for end of level
while queue is not empty:
node = queue.dequeue()
if node is null:
if queue is not empty:
queue.enqueue(null) // Add marker for next level
else:
if queue.front() is null: // First node at this level
result.append(node.value)
if node.left:
queue.enqueue(node.left)
if node.right:
queue.enqueue(node.right)
return result
C++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
vector<int> leftView(Node* root) {
vector<int> result;
if (root == nullptr) return result;
queue<Node*> q;
q.push(root);
q.push(nullptr); // Marker for end of level
while (!q.empty()) {
Node* current = q.front();
q.pop();
if (current == nullptr) {
if (!q.empty()) {
q.push(nullptr); // Add marker for next level
}
} else {
if (q.front() == nullptr) { // First node at this level
result.push_back(current->data);
}
if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
}
return result;
}
int main() {
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
vector<int> result = leftView(root);
for (int val : result) {
cout << val << " ";
}
return 0;
}
Java
import java.util.*;
class BinaryTree {
static class Node {
int data;
Node left, right;
Node(int val) {
data = val;
left = right = null;
}
}
public static List<Integer> leftView(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<Node> q = new LinkedList<>();
q.add(root);
q.add(null); // Marker for end of level
while (!q.isEmpty()) {
Node current = q.poll();
if (current == null) {
if (!q.isEmpty()) q.add(null); // Add marker for next level
} else {
if (q.peek() == null) { // First node at this level
result.add(current.data);
}
if (current.left != null) q.add(current.left);
if (current.right != null) q.add(current.right);
}
}
return result;
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
List<Integer> result = leftView(root);
for (int val : result) {
System.out.print(val + " ");
}
}
}
Python
from collections import deque
class Node:
def __init__(self, val):
self.data = val
self.left = None
self.right = None
def left_view(root):
if root is None:
return []
result = []
queue = deque([root, None]) # Add marker for end of level
while queue:
node = queue.popleft()
if node is None:
if queue:
queue.append(None) # Add marker for next level
else:
if queue[0] is None: # First node at this level
result.append(node.data)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print(left_view(root))
Explanation
- Defines a Node structure with data, left, and right pointers, initializing with a given value.
- Uses a queue for level-order traversal, with a nullptr marker to mark the end of each level.
- Adds the first node at each level (leftmost node) to the result vector for the left view.
Output
1 2 4
Time & Space Complexity
| Method |
Time Complexity |
Space Complexity |
| Recursion (DFS) |
O(n) |
O(n) |
| Level Order Traversal (BFS) |
O(n) |
O(n) |
| Using Queue and Null Pointer |
O(n) |
O(n) |
Conclusion
In conclusion, the left view of binary tree is beneficial for knowing the view of the tree. It can be calculated with different methods, such as recursion (DFS), level order traversal (BFS), and using a queue and null pointer. All these are useful for various situations, the similarity being that we consider the first node at every level. Knowing the complexity of time and space helps select the best solution for a problem.
Equip Yourself with Industry-Relevant Skills for a Successful Tech Career!
Explore ProgramFrequently Asked Questions
1. What is the left view of a binary tree?
The left view of a binary tree consists of those nodes visible when one sees the tree from the left side. It is a linear view of each level's first node from top to bottom.
2. What is the left of the binary search tree?
The left of a binary search tree is the left subtree rooted at the root's left child. Nodes of the left subtree of a node in a BST have keys smaller than the node.
3. What is the left child of a binary tree?
The left child of a binary tree is a node that is connected directly to the parent node using the left pointer. It is less than in value in binary search trees but depends on the tree type.
4. What is binary tree left rotation?
Binary tree left rotation is when the root node is shifted to the left and the new root becomes its right child. This preserves binary search tree properties while balancing the tree.
.avif)
