Convert String to ZigZag Bottom Up

 Posted on March 30, 2016  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) Example P A H N A P L S I I G Y I R ```And then read line by line: `"PAHNAPLSIIGYIR"` Write the code that will take a string and make this conversion given a number of rows: string convert(string text, int nRows); ````convert(“PAYPALISHIRING”, 3) should return "PAHNAPLSIIGYIR"`. [Read More]
String  zigzag  leetcode 

Asymptotic Notation

 Posted on March 11, 2016  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Its been a while, since I have blogged. To start with I am posting a basics of asymptotic analysis of algorithm, which we study at the start of the course. Now we are going to be less precise and worry only about approximate answers for large inputs. The Big-Oh Notation Definition: Let f(n) and g(n) be real-valued functions of a single non-negative integer argument. We write f(n) is O(g(n)) if there is a positive real number c and a positive integer n0such that f(n)≤cg(n) for all n≥n0. [Read More]
Algorithms  AlgorithmAnalysis 

Growth Rate - The Importance of Asymptotics

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

It really is true that if algorithm A is o(algorithm B) then for large problems A will take much less time than B. Definition: If (the number of operations in) algorithm A is o(algorithm B), we call A asymptotically faster than B. Example:: The following sequence of functions are ordered by growth rate, i.e., each function is little-oh of the subsequent function. log(log(n)), log(n), (log(n))2, n1/3, n1/2, n, nlog(n), n2/(log(n)), n2, n3, 2n, 4n, n! [Read More]
Algorithms  AlgorithmAnalysis 

Given a BST with 2 nodes swapped, fix it

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem Given a BST with 2 nodes swapped fix it. Example Consider the BST: Following is the correct BST 10 / \\ 5 20 / \\ 2 8 Now we swap 8 and 20, and BST is changed. Input Tree: 10 / \\ 5 8 / \\ 2 20 In the above tree, nodes 20 and 8 must be swapped to fix the tree. ```In the [previous post](http://k2code.blogspot.in/2015/09/given-binary-search-tree-with-2-nodes.html), we saw how many pairs in the input tree violate the BST property. [Read More]
inorder  binary-search-tree  BST 

Given a binary search tree with 2 nodes swapped find number of pairs not following BST properties

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Given a binary search tree with 2 nodes swapped, give the number of nodes not following bst property. Follow up - Fix the BST, in the next post. Example Consider the BST: Following is the correct BST 10 / \\ 5 20 / \\ 2 8 Now we swap 8 and 20, and BST is changed. Input Tree: 10 / \\ 5 8 / \\ 2 20 In the above tree, nodes 20 and 8 must be swapped to fix the tree. [Read More]
inorder  Inorder traversal  bank-bazaar  binary-search-tree  BST  count 

For a Given node of a binary tree, print the K distance nodes.

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

Problem You are given a function printKDistanceNodes which takes in a root node of a binary tree, a start node and an integer K. Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted order. Distance can be upwards or downwards. Example start node = 18, k = 2 , then output = 2, 19, 25 [Read More]
Binary Tree  BT  kodeknight  K-Distance  distance 

Print all nodes that are at distance k from a leaf node

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node. Here the meaning of distance is different from previous post. Here k distance from a leaf means k levels higher than a leaf node. For example if k is more than height of Binary Tree, then nothing should be printed. Expected time complexity is O(n) where n is the number nodes in the given Binary Tree. [Read More]
Binary Tree  BT  K-Distance  distance 

Find the distance between 2 nodes in Binary Tree

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

cant the solution be simply distance of n1 and n2 …

Rohit Yadav - Feb 0, 2016

cant the solution be simply distance of n1 and n2 from lca.
dist(n1,n2)= dist(lca,n1)+dist(lca,n2)? correct me if i am wrong.

You are absolutely correct. What is being done in the above solution is, dist(n1,n2) = dist(root,n1) + dist(root,n2) - 2*dist(root,lca) as root is point of reference. Thanks.

Binary Tree  BT  kodeknight  least-common-ancestor  LCA  distance 

Find the distance between 2 nodes in Binary Tree

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Find the distance between two keys in a binary tree, no parent pointers are given. Distance between two nodes is the minimum number of edges to be traversed to reach one node from other. Example Dist(-4,3) = 2, Dist (-4,19) = 4 Dist(21,-4) = 3 Dist(2,-4) = 1 Solution The distance between two nodes can be obtained in terms of lowest common ancestor. Following is the formula. Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2\*Dist(root, lca) 'n1' and 'n2' are the two given keys 'root' is root of given Binary Tree. [Read More]
Binary Tree  BT  kodeknight  least-common-ancestor  LCA  distance 

Program to count leaf nodes in a binary tree

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Count leaf nodes in a binary tree Solution Method 1 - Recursive Here is the logic: If node is NULL then return 0. Else If left and right child nodes are NULL return 1. Else recursively calculate leaf count of the tree using below formula. Leaf count of a tree = Leaf count of left subtree + Leaf count of right subtree Here is the recursive solution: [Read More]
Binary Tree  BT  kodeknight  count