Day 04 & 05: Coding Problems

I solved 6 problems from the topics Recursion and Binary Tree:

1. Generate all Binary Strings (Recursion)
2. Left View of Binary Tree
3. Right View of Binary Tree
4. Symmetric Binary Tree
5. Top View of Binary Tree
6. Bottom View of Binary Tree

Problem 1: Generate all Binary Strings

Context

The problem requires generating and printing all binary strings of a given length N that do not contain consecutive 1s. A binary string consists only of the characters 0 and 1. The output should include all possible valid binary strings of size N that meet the specified condition.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses a recursive backtracking approach to generate all binary strings of a specified length N that do not contain consecutive 1s. Here's what the code does:

1. The function constructs binary strings by making two recursive calls at each step: one for adding 0 and one for adding 1 (only if the previous bit is 0 to avoid consecutive 1s).
2. The bit variable is crucial for keeping track of the last added bit. If the previously added bit is 1, the next bit cannot be 1 to prevent consecutive 1s.
3. The base case ensures that when the length n reaches zero, the constructed string s is complete and added to the result list.

This approach systematically explores all possible combinations while enforcing the condition of no consecutive 1s.

Problem 2: Left View of Binary Tree

Context

The problem is to find the left view of a given binary tree. The left view of a binary tree is defined as the set of nodes visible when the tree is viewed from the left side. The task is to complete the function leftView(), which takes the root of the binary tree as an argument and returns the left view of the tree as a list of node values. If the tree is empty, the function should return an empty list.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code used preorder traversal (root, left, right) to compute the left view of a binary tree. Here’s what the code does:

1. The traverse function ensures that each level is visited starting from the root, then the left child, and finally the right child.
2. The 'lv' vector keeps track of the leftmost nodes for each level.
3. Each element of 'lv' represents the leftmost child at that level of the tree and is stored at the corresponding index in 'lv'.
4. The leftmost node at each level is added to the 'lv' vector by checking if the current level matches the size of 'lv'.
5. This condition ensures that only the leftmost node at each level is stored in the'lv'. If the current level is already represented in 'lv', it means the leftmost node from that level has already been added, so it is not added again.
6. Preorder traversal is used to ensure that the root node is processed first, followed by the left subtree, which helps in capturing the left view of the binary tree efficiently.

This approach ensures that the leftmost element at each level is stored, giving the correct left view of the binary tree.

Problem 3: Right View of Binary Tree

Context

The problem is to determine the right view of a binary tree. Given the root of the tree, you need to return a list of node values that would be visible if you were standing on the right side of the tree. The nodes should be listed in order from the top to the bottom of the tree.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The solution is almost the same as the left view binary tree solution, except that it processes the right child before the left child, ensuring that the rightmost node at each level is stored in the result vector.

The given code used reverse preorder traversal (root, right, left) to compute the right view of a binary tree. Here’s what the code does:

1. The traverse function ensures that each level is visited starting from the root, then the right child, and finally the left child.
2. The 'rv' vector keeps track of the rightmost nodes for each level.
3. Each element of 'rv' represents the rightmost child at that level of the tree and is stored at the corresponding index in 'rv'.
4. The rightmost node at each level is added to the 'rv' vector by checking if the current level matches the size of the 'rv'.
5. This condition ensures that only the rightmost node at each level is stored in the'rv'. If the current level is already represented in 'rv', it means the rightmost node from that level has already been added, so it is not added again.
6. Reverse preorder traversal is used to ensure that the root node is processed first, followed by the right subtree, which helps in capturing the right view of the binary tree efficiently.

This approach ensures that the rightmost element at each level is stored, giving the correct right view of the binary tree.

Problem 4: Symmetric Binary Tree

Context

The problem is to determine whether a given binary tree is symmetric around its center. Given the root of the tree, you need to check if the tree is a mirror image of itself. This means that the left and right subtrees are identical when viewed as reflections of each other.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code checks whether a binary tree is symmetric around its center. Here’s what the code does:

1. The isSymmetric function initiates this process by calling 'prove' on the left and right children of the root node.
2. The 'prove' function determines whether two given subtrees (t1 and t2) are symmetric by recursively comparing their respective children.
3. It checks if the left child of t1 is symmetric with the right child of t2, and if the right child of t1 is symmetric with the left child of t2.
4. The base cases ensure that the function handles scenarios where one or both subtrees are empty or have different values.

This code effectively checks for symmetry in a binary tree by leveraging recursive comparisons, ensuring that each level of the tree mirrors itself around the center.

Problem 5: Top View of Binary Tree

Context

The task is to determine and print the top view of a binary tree. The top view consists of the set of nodes visible when the tree is viewed from above. For each vertical level of the tree, only the first node encountered from the top is included in the top view. If two nodes are on the same vertical level and both are visible from the top, only the leftmost one is included. The output should list the nodes from the leftmost to the rightmost node.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses level order traversal to compute the top view of a binary tree. Here's what the code does:

1. The Level Order Traversal ensures that nodes are processed level by level while keeping track of the horizontal distance from the root, which is essential for correctly determining the top view.
2. A map is used to store the first node encountered at each horizontal distance.
3. Before storing the node in the map, first, it is checked if the current horizontal distance (level) is not already in the map. If it is not, it means this is the first node encountered at this horizontal distance, so its data is added to the map.
4. The result is built by iterating over the map and collecting the stored node values, which represent the top view of the tree.
5. The top view is then returned as a vector of node values.

This approach efficiently computes the top view of the tree. It ensures that only the necessary nodes are included, providing an optimal solution.

Problem 6: Bottom View of Binary Tree

Context

Given a binary tree, the task is to print the bottom view from left to right. A node is included in the bottom view if it can be seen when the tree is viewed from the bottom. In the bottom view, if multiple nodes share the same horizontal distance from the root, the node that appears last in the level-order traversal should be printed. The goal is to output the nodes visible from the bottom perspective, ordered from the leftmost to the rightmost.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The approach used in this code is quite similar to the one used for finding the top view of a binary tree.

The given code uses level order traversal to compute the bottom view of a binary tree. Here's what the code does:

1. The Level Order Traversal ensures that nodes are processed level by level while keeping track of the horizontal distance from the root, which is essential for correctly determining the bottom view.
2. A map is used to store the last node encountered at each horizontal distance. This ensures that the most recent (bottommost) node at each horizontal distance is included in the bottom view.
3. The map is updated without checking the previous nodes at that horizontal distance to reflect the most recent node encountered at each distance distance.
4. The result is built by iterating over the map and collecting the stored node values, which represent the bottom view of the tree.
5. The bottom view is then returned as a vector of node values.

This approach efficiently computes the bottom view of the tree. It ensures that only the recent nodes are included, providing an optimal solution.

Here are the six problems I solved today and yesterday. I look forward to sharing more coding challenges with you tomorrow??