Inorder traversal

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]

Given a binary tree with extra field "next pointer" in node, populate the next pointer to the nodes inorder successor

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

Problem : Given a Binary tree where each node has an extra field (node * next), write a function that puts the inorder successor of that node in the next pointer. This is how our binary tree node looks like : struct node { int data; struct node\* left; struct node\* right; struct node\* next; } Initially, all next pointers have NULL values. Your function should fill these next pointers so that they point to inorder successor. [Read More]

inorder Binary Tree BT kodeknight Amazon inorder successor Inorder traversal

Binary Tree In-Order Traversal - Recursive and Iterative Solution

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

Consider the tree Inorder traversal prints the binary tree in increasing order in case of Binary Search Tree, but here we are discussing any binary tree. To traverse a binary tree in Inorder, following operations are carried-out : Traverse the left most subtree starting at the left external node, Visit the root, and Traverse the right subtree starting at the left external node. Therefore, the Inorder traversal of the above tree will outputs: [Read More]

inorder Binary Tree BT kodeknight incomplete Inorder traversal

Binary tree traversal: Preorder, Inorder, Post-order, BFS, DFS, Level Order, zig zag order

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

In order to illustrate the 3 traversals - pre order, in-order and post-order lets take following tree: Preorder traversal: To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree. Therefore, the Preorder traversal of the above tree will outputs: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10 Implementing pre-order traversal [Read More]

inorder Preorder traversal Binary Tree BT kodeknight postorder preorder incomplete Inorder traversal traversal binary-search-tree BST Postorder traversal

Threaded binary tree

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

Since traversing the three is the most frequent operation, a method must be devised to improve the speed. In case of iterative traversal, speed is less than recursive one. So we cans use Threaded tree. If the right link of a node in a tree is NULL, it can be replaced by the address of its inorder successor. This tree is called right in-threaded binary tree. An extra field called the rthread is used. [Read More]

inorder tree Algorithms kodeknight inorder successor Inorder traversal binary-search-tree BST Threaded binary Tree

Inorder successor OR Predecessor of BST node

Posted on August 28, 2009 (Last modified on August 7, 2020) | 2 minutes | Kinshuk Chandra

It is important to understand inorder successor of BST because it helps us understand deletion of node from a tree, when the node deleted has 2 children. To find the inorder successor of node u: If u has a right child, r, then succ(u) is the leftmost descendent of r Otherwise, succ(u) is the closest ancestor, v, of u (if any) such that u is descended from the left child of v. [Read More]

inorder tree kodeknight Data Structures DS inorder successor Inorder traversal binary-search-tree BST