Tag: Intro

Kahn’s Topological Sort Algorithm

Given a directed acyclic graph (DAG), print it in Topological order using Kahn’s Topological Sort algorithm. If the DAG has more than one topological ordering, print any of them.

Search given key in BST | Recursive & Iterative Solution

Given a BST, write an efficient function to search a given key in it. The algorithm should return the parent node of the key and print if the key is left or right node of the parent node. If the key is not present in the BST, the algorithm should be able to determine that.

Insertion in BST | Recursive & Iterative Solution

  A Binary Search Tree (BST) is a rooted binary tree, whose nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree should satisfy the BST property, which states that the key in each node must be greater than all keys stored …

Inorder Tree Traversal | Iterative & Recursive

Given a binary tree, write iterative and recursive solution to traverse the tree using in-order traversal.   Unlike linked lists, one-dimensional arrays and other linear data structures, which are traversed in linear order, trees may be traversed in multiple ways in depth-first order (in-order, pre-order and post-order) or breadth-first order (level order traversal). Beyond these …

Preorder Tree Traversal | Iterative & Recursive

Given a binary tree, write iterative and recursive solution to traverse the tree using pre-order traversal.   Unlike linked lists, one-dimensional arrays and other linear data structures, which are traversed in linear order, trees may be traversed in multiple ways in depth-first order (pre-order, pre-order and pre-order) or breadth-first order (level order traversal). Beyond these …

Postorder Tree Traversal | Iterative & Recursive

Given a binary tree, write iterative and recursive solution to traverse the tree using post-order traversal.   Unlike linked lists, one-dimensional arrays and other linear data structures, which are traversed in linear order, trees may be traversed in multiple ways in depth-first order (post-order, pre-order and post-order) or breadth-first order (level order traversal). Beyond these …

Level Order Traversal of Binary Tree

Given a binary tree, print its nodes level by level. i.e. all nodes present at level 1 should be printed first followed by nodes of level 2 and so on.. All nodes for any level should be printed from left to right.

Merge Sort Algorithm for Singly Linked List

Given a linked list, sort it using merge sort algorithm.     Email Address Merge sort algorithm is an efficient, general-purpose sorting algorithm which produces a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a comparison sort, i.e. it can sort items …