Crack the Coding Interview

Trees can have any number of children, but the simplest and most common type of tree is a binary tree, where each node has at most two child nodes (called left child and right child). In other words, a node in a binary tree can have 0 or 1 or 2 child nodes.

Given the root of a binary tree, write a program to check whether it is a valid binary search tree (BST) or not. A BST is valid if all nodes in the left subtree have values less than the node’s value, all nodes in the right subtree have values greater than the node’s value, and both left and right subtrees are also binary search trees.

Given two strings str1 and str2 of size m and n, write a program to check whether the two strings are an anagram of each other or not. A string str1 is an anagram of str2 if the characters of str1 can be rearranged to form str2.

Divide and conquer is a recursive problem-solving approach that divides the problem into smaller subproblems, recursively solves the subproblems, and combines the solutions to the subproblems to get the solution of the original problem.

In this blog, we will learn how to use segment trees for efficient point and range updates. For the point update query, update(idx, val), we need to increment the element at the index idx from the original array by val, i.e. arr[idx] = arr[idx] + val. For the range update query, update(l, r, val), we must increment all the elements from index l to r from the original array by val.

Merge sort is one of the fastest comparison-based sorting algorithms, which works on the principle of the divide and conquer approach. The worst and best case time complexity of merge sort is O(nlogn), and space complexity is O(n). It is also the best algorithm for sorting linked lists.