## What is a Tree?

A tree is an abstract data type which is structured like a tree. It has a root node with 2 or more branches offshooting from the root. It can be represented recursively such as each of the node can act as a root in itself. Example below. There can be multiple implementations of the Tree ADT(abstract data type) like Binary tree, Binary Search tree. ...

## What is a Binary Tree?

A Binary Tree is a Tree based data structure in which each node can have at most two children referred to as Left child and Right child. It can be localized in the same manner node, left child and right child and normally represented as LNR where L & R are left and right children respectively and N is the node. An example is below. Binary trees can...

## How would you store a Binary Tree?

A Binary tree can be stored in 2 possible ways. 1. Nodes and References : You can create a Node class with node reference variables for the left and right child. Any or both can be null as and when required. class Node{ int value; Node left; Node right; } 2. Array : You can store binary tree in a breadth first order using an array. The log...

## What is a Binary Search Tree?

Binary Search Tree, popularly known as BST, is a sorted Binary Tree. They are suited for lookup using Binary Search. Like Binary Trees BSTs can also be localized to a left child, node, right child (LNR). The general rule of thumb followed in case of BST will be the sorted order of the same L

## How would you insert an element into a Binary Search Tree?

Insertion into a Binary Search Tree will happen using the rule of L

## How would you search in a Binary Search Tree?

The search in a Binary Search Tree would happen on the Binary search algorithm since the data in a BST is sorted. You enter the search through the root node and depending on if the search value is greater than or smaller than the root value you would move down the right or the left tree. You can search this recursively as explained in the example b...

## How can you traverse a Binary Tree?

A binary tree can be traversed in three ways. 1. In Order traversal: The order of traversal is essentially L->N->R. So you traverse the left sub tree before you read the node and then you traverse the right sub tree. 2. Pre Order traversal: The order of traversal in this case is N->L->R. Traverse the node then the left subtree and then the right su...

## Tree traversal examples for Binary Search Tree

The example of the BST and normal Binary tree traversals below The tree on which we will execute the traversal is as follows. We have used a stringbuffer object to get the nodes which have been traversed. This will help us if we want to print the tree in any of these 3 orders. The TreeNode class defined in previous examples have been modified to ha...

## How would you perform deletion in a Binary Search Tree?

Unlike insertion, deletion is a wee bit complex when it comes to Binary Search Trees. That's because while insertion you don't need to worry about rearranging the BST, you just find its correct location and done. The node will always be added as a leaf node. On the other hand in deletion you may have the need to delete any non leaf node as well and...

## How would you mirror a Binary tree?

Mirroring a binary tree is a problem asked in a lot of interviews and we will be tackling it in a simple but efficient manner. Any tree related problem should be attempted to be solved in a recursive approach since Tree is a localized data structure i.e small trees make up large trees. Here in this example we will take a case of Binary Search Tree ...

## Convert a binary tree to a singly linked list

Why would anyone convert a binary tree to a linked list? Interviewer asking this question expects your understanding of Binary Tree traversals to be top notch. The key here is you parse the nodes through in-order traversal and move them to the right side of the tree. The image below shows what I said and the code will do this recursively   Resultan...

## Tree Traversals video tutorial

A Binary Tree can be traversed in different ways. Following are the generally used ways for traversing trees. (a)  Inorder (b)  Preorder (c)  Postorder Check the awesome explanation of tree traversal by Tushar Roy To check out simple text based explanation click here