Eat Code Sleep – repeat
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
A Topological sort of a Directed-Acyclic graph G is a linear ordering of all its vertices such that if G contains an edge E (u, v), then u appears before v in the ordering. And if the graph is not acyclic, then no linear ordering is possible.
Mirror images mean right and left child of the two trees are interchanged. Thus, left child of first tree is right child of second tree. Traverse the Tree 1 and Tree 2 in Inorder fashion and store the node values of each Tree 1 & Tree 2 in two different arrays.
This problem was asked in February challenge 2014. Around 900 people were able to solve this problem.
It’s not very intuitive for beginners. And also not very straightforward for someone not doing competitive programming.
Time Complexity is the number of primitive operations executed on a particular input. It measures the amount of time an algorithm takes to complete as a function of the length of the input.
Quicksort is a sorting algorithm whose worst-case running time is O(n^2), for an input of size n. Quicksort, in spite of having worse time complexity than Merge Sort which is O(nlogn), it is a better practical choice for sorting. This is because it is remarkably efficiently on average cases, where its time complexity is O(nlogn).
Sorting means arranging a set of data in an order. There’re various algorithms to sort the data (in a data structure) in increasing or decreasing order. These algorithms can be divided on basis of various factors. Inplace sorting means that all the data which is to be sorted can be accommodated at a time in memory. Examples of inplace sorting algorithms are Selection sort, Bubble sort etc.
DFS (Depth-First Search) is an algorithm for traversing a graph. DFS starts from source vertex (graph) or root (in trees) and then visits an unvisited adjacent node v. After that it checks if node v has any adjacent node which is unvisited. If it reaches a leaf node or any node having no unvisited adjacent node. It backtracks and continue traversing other nodes.
BFS (Breadth-First Search) is one of the simplest algorithms for traversing a graph. Prim’s min-spanning-tree and Djikstra’s algorithm use similar ideas as BFS. BFS is also known as Level-order traversal because the algorithm discover all nodes at distance k from root before discovering any nodes at distance k+1.
Update query (Range min query) For update query, we are given an index which needs to be updated. Let val be the value needed to be changed of a given node x. We start from the root of the segment tree and update all nodes (containing minimum value from given index) which have given index in their range. If a node doesn’t have a given index in its range, we don’t make any changes to that node.