You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes Create an algorithm to decide if T2 is a subtree of T1

 Posted on March 21, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes Create an algorithm to decide if T2 is a subtree of T1 Solution Method 1 - Brute force Traverse T1. If the current node is equal to the root node of T2, traverse both of the trees (T2 and the current subtree of T1) at the same time. Compare the current node. [Read More]
tree  kodeknight  CrackingTheCodingInterview 

Minimum Spanning tree MST

 Posted on October 19, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

MST is used to connect a bunch of points to each other as cheaply as possible. Applications clustering networking Blazingly fast greedy algorithms There are many greedy algorithm, but we will talk about 2: Prim’s algo [1957, also djikstra’ 1959] or Jarnic found it in 25 years earlier. Kruskal’s algo[1956]. Will be using union find data-structure. They are blazingly fast as they are almost close to linear time of number of edges: [Read More]
tree  kodeknight  greedy Algo  minimum-spanning-tree  MST  spanning tree  graph-search 

AVL Tree Index

 Posted on August 25, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

hell-o, im carloe distor, from the most beautiful … Anonymous - Mar 3, 2014hell-o, im carloe distor, from the most beautiful province in benguet, baguio city, i would like to ask if you can do me a favor, because im so tired in doing my homework , IN BINARY TREE (ARRAY REPRESENTATION), INFIXTOPOSTFIX USING STACK AND AVL , THANK YOU, Hi , I don’t think I will be able to help much. [Read More]
tree  kodeknight  balanced trees  avl 

Topological Sorting

 Posted on August 4, 2013  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Definition Topological sort: an ordering of the vertices in a directed acyclic graph, such that: If there is a path from u to v, then v appears after u in the ordering. A topological ordering of a directed graph G is a labeling f of G’s nodes (1…n) such that: (1) the f(v)’s are the set {1, 2, … , n} (2) if (u, v) in G, then f(u) < f(v) … the graph should move in forward direction. [Read More]
Graph  tree  kodeknight  sorting  DFS  incomplete  graph-search 

Red Black Tree – Insertion

 Posted on January 7, 2012  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Introduction: Please refer the introduction of RBT here. So, we now know the invariants or properties of RBT which make it rbt :) Insertion of element in RBT or red black tree breaks one of the 4 invariants or properties. So we have to fix it in minimal possible way. To assist us with we have 2 solutions : Flipping the color Right and left rotation Insertion: Insertion begins by adding the node much as binary search tree insertion does and by coloring it red. [Read More]
tree  kodeknight  red-black-tree  RBT  balanced trees  incomplete 

Red Black Tree – Deletion

 Posted on January 7, 2012  (Last modified on August 7, 2020)  |  8 minutes  |  Kinshuk Chandra

Deletion of a node from a red black tree is very difficult. During insertion we selected the color of a new node as red to make it easier. We forced a red violation and fixed it. Red violations are easy to fix, and we took full advantage of that to produce a truly elegant recursive algorithm. When you want to delete a node, you don’t have the option of choosing its color. [Read More]
tree  kodeknight  red-black-tree  RBT  balanced trees 

AVL Tree : Rotations

 Posted on January 6, 2012  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

A tree rotation can be an imtimidating concept at first. You end up in a situation where you’re juggling nodes, and these nodes have trees attached to them, and it can all become confusing very fast. I find it helps to block out what’s going on with any of the subtrees which are attached to the nodes you’re fumbling with, but that can be hard. Left Rotation (LL) or Single Left rotation [Read More]
tree  kodeknight  balanced trees  avl