Kamal Rawat's Blog, page 6

Dynamic Programming concept

The basic idea of DP is applicable to problems that can be thought in terms of recursion. For example, consider problem of computing n’th fibonacci term: This is a recursive definition (Fib(n) is given in terms of Fib(n-1)) and can be adopted in the form of a function in a straight-forward way: int fib(int n) { […]

Radix Sort

Consider an array that stores account numbers of all employees. One unique thing about account numbers is that they have equal number of digits. Let us take example where, account numbers are three digits long, and array has 6 account numbers are shown below int arr[ ] = {582, 675, 591, 189, 900, 770} Range […]

Sum of all the nodes in a tree

Given a binary tree, where each node is having an integer value. Write a function that accept the root of this tree and returns the sum of all the nodes in the tree. The sum of all the nodes in the Solution: Like other Binary tree questions, this one also use recursion. The signature of […]

Count number of zeros in a Row-wise Col-wise sorted binary matrix

Given a binary matrix with all rows and col sorted. Write code to count the number of zeros in that matrix. For example, if the matrix is [0, 0, 0, 0, 1] [0, 0, 0, 1, 1] [0, 1, 1, 1, 1] [0, 1, 1, 1, 1] [1, 1, 1, 1, 1] Then output should […]

Iterative pre-order traversal using stack

We have seen the in-order traversal of a binary tree. It is a recursive code. Recursion stack can be simulated using an explicit Stack data structure and keeping the function non-recursive. Let us see how: When a function calls itself, its activation record (stack frame) is pushed in the function call stack of memory. The […]

Right view of a binary tree

Write code to print the right-view of a binary tree. Right-view of the tree is the nodes visible when the tree is seen from the right side. If there are two nodes at the same level, then only the right-most node will be visible in the right-view as shown below: Solution: If we traverse the […]

Left view of a binary tree

Write code to print the left-view of a binary tree. Left-view of the tree is the nodes visible when the tree is seen from the left side. If there are two nodes at the same level, then only the left-most node will be visible in the left-view as shown below: Solution: While traversing the tree […]