I am wondering what the particular applications of binary trees are.  Could you give some real examples?

What are the applications of binary trees?

Can anyone please explain the difference between **binary tree** and **binary search tree** *with an example*?


Difference between binary tree and binary search tree

I recently came across the data structure known as a [_skip list_](http://en.wikipedia.org/wiki/Skip_list). It seems to have very similar behavior to a binary search tree. 

Why would you ever want to use a skip list over a binary search tree? 

Skip List vs. Binary Search Tree

What is the difference between a heap and BST? 

When to use a heap and when to use a BST? 

If you want to get the elements in a sorted fashion, is BST better over heap?

Heap vs Binary Search Tree (BST)

How can I print a binary tree in Java so that the output is like:

       4 
      / \ 
     2   5 

My node:

    public class Node&lt;A extends Comparable&gt; {
        Node&lt;A&gt; left, right;
        A data;
	
        public Node(A data){
            this.data = data;
        }
    }


How to print binary tree diagram in Java?

I&#39;m trying to find the definition of a binary search tree and I keep finding different definitions everywhere. 

Some say that for any given subtree the left child key is less than or equal to the root.

Some say that for any given subtree the right child key is greater than or equal to the root.

And my old college data structures book says &quot;every element has a key and no two elements have the same key.&quot;

Is there a universal definition of a bst? Particularly in regards to what to do with trees with multiple instances of the same key.

EDIT: Maybe I was unclear, the definitions I&#39;m seeing are

1) left &lt;= root &lt; right

2) left &lt; root &lt;= right

3) left &lt; root &lt; right, such that no duplicate keys exist.

Are duplicate keys allowed in the definition of binary search trees?

The Binary Tree here is may not necessarily be a Binary Search Tree.  
The structure could be taken as -

    struct node {
        int data;
        struct node *left;
        struct node *right;
    };

The maximum solution I could work out with a friend was something of this sort -  
Consider [this binary tree](http://lcm.csa.iisc.ernet.in/dsa/node87.html) :

[![Binary Tree][1]][1]

The inorder traversal yields - 8, 4, 9, 2, 5, 1, 6, 3, 7

And the postorder traversal yields - 8, 9, 4, 5, 2, 6, 7, 3, 1

So for instance, if we want to find the common ancestor of nodes 8 and 5, then we make a list of all the nodes which are between 8 and 5 in the inorder tree traversal, which in this case happens to be [4, 9, 2]. Then we check which node in this list appears last in the postorder traversal, which is 2. Hence the common ancestor for 8 and 5 is 2.

The complexity for this algorithm, I believe is O(n) (O(n) for inorder/postorder traversals, the rest of the steps again being O(n) since they are nothing more than simple iterations in arrays). But there is a strong chance that this is wrong. :-)

But this is a very crude approach, and I&#39;m not sure if it breaks down for some case. Is there any other (possibly more optimal) solution to this problem?


  [1]: https://i.stack.imgur.com/Sz5KZ.gif

How to find the lowest common ancestor of two nodes in any binary tree?

Can someone please help me understand the following Morris inorder tree traversal algorithm without using stacks or recursion ? I was trying to understand how it works, but its just escaping me.
    
     1. Initialize current as root
     2. While current is not NULL
      If current does not have left child     
       a. Print current’s data
       b. Go to the right, i.e., current = current-&gt;right
      Else
       a. In current&#39;s left subtree, make current the right child of the rightmost node
       b. Go to this left child, i.e., current = current-&gt;left


I understand the tree is modified in a way that the `current node`, is made the `right child` of the `max node` in `right subtree` and use this property for inorder traversal. But beyond that, I&#39;m lost.

EDIT:
Found this accompanying c++ code. I was having a hard time to understand how the tree is restored after it is modified. The magic lies in `else` clause, which is hit once the right leaf is modified. See code for details:

	/* Function to traverse binary tree without recursion and
	   without stack */
	void MorrisTraversal(struct tNode *root)
	{
	  struct tNode *current,*pre;
	 
	  if(root == NULL)
		 return; 
	 
	  current = root;
	  while(current != NULL)
	  {
		if(current-&gt;left == NULL)
		{
		  printf(&quot; %d &quot;, current-&gt;data);
		  current = current-&gt;right;
		}
		else
		{
		  /* Find the inorder predecessor of current */
		  pre = current-&gt;left;
		  while(pre-&gt;right != NULL &amp;&amp; pre-&gt;right != current)
			pre = pre-&gt;right;
	 
		  /* Make current as right child of its inorder predecessor */
		  if(pre-&gt;right == NULL)
		  {
			pre-&gt;right = current;
			current = current-&gt;left;
		  }
		  
	 	 // MAGIC OF RESTORING the Tree happens here: 
		  /* Revert the changes made in if part to restore the original
			tree i.e., fix the right child of predecssor */
		  else
		  {
			pre-&gt;right = NULL;
			printf(&quot; %d &quot;,current-&gt;data);
			current = current-&gt;right;
		  } /* End of if condition pre-&gt;right == NULL */
		} /* End of if condition current-&gt;left == NULL*/
	  } /* End of while */
	}


Explain Morris inorder tree traversal without using stacks or recursion

Which is the best data structure that can be used to implement a binary tree in Python?

How to implement a binary tree?

I realized recently that while having used BST&#39;s plenty in my life, I&#39;ve never even contemplated using anything but Inorder traversal (while I am aware of and know how easy it is to adapt a program to use pre/post-order traversal).

Upon realizing this, I pulled out some of my old data-structures textbooks and looked for the reasoning behind the usefulness of pre-order and post-order traversals - they didn&#39;t say much though.

**What are some examples of when to use preorder/postorder practically?  When does it make more sense than in-order?**

When to use Preorder, Postorder, and Inorder Binary Search Tree Traversal strategies

It&#39;s been a while from those school years. Got a job as IT specialist at a hospital.  Trying to move to do some actual programming now.  I&#39;m working on binary trees now, and I was wondering what would be the best way to determine if the tree is height-balanced.  

I was thinking of something along this:

	public boolean isBalanced(Node root){
        if(root==null){
		    return true;  //tree is empty
		}
		else{
			int lh = root.left.height();
			int rh = root.right.height();
			if(lh - rh &gt; 1 || rh - lh &gt; 1){
				return false;
			}
		}
		return true;
	}


Is this a good implementation? or am I missing something?

How to determine if binary tree is balanced?

I need to find the kth smallest element in the binary search tree without using any static/global variable. How to achieve it efficiently?
The solution that I have in my mind is doing the operation in O(n), the worst case since I am planning to do an inorder traversal of the entire tree. But deep down I feel that I am not using the BST property here. Is my assumptive solution correct or is there a better one available ?

Find kth smallest element in a binary search tree in Optimum way

For binary search tree type of data structures, I see the Big O notation is typically noted as O(logn).  With a lowercase &#39;l&#39; in log, does this imply log base e (n)  as described by the natural logarithm?  Sorry for the simple question but I&#39;ve always had trouble distinguishing between the different implied logarithms.

Is Big O(logn) log base e?

I am confused about the terminology of the below trees, I have been studying the Tree, and I am unable to distinguish between these trees:
 
 **a) Complete Binary Tree**

 **b) Strict Binary Tree**

 **c) Full Binary Tree** 

Please help me to differentiate among these trees.
When and where these trees are used in Data Structure?

Difference between &quot;Complete binary tree&quot;, &quot;strict binary tree&quot;,&quot;full binary Tree&quot;?

**For Binary trees:** There&#39;s no need to consider tree node values, I am only interested in different tree topologies with &#39;N&#39; nodes.

**For Binary Search Tree:** We have to consider tree node values.

With &#39; N &#39; no of nodes, how many different Binary and Binary Search Trees possible?

What algorithms can be used to draw a binary tree in the console? The tree is implemented in C. For example, a BST with numbers: 2 3 4 5 8 would be shown in the console as:

![alt text][1]


  [1]: http://i.stack.imgur.com/8a1M8.jpg

C How to &quot;draw&quot; a Binary Tree to the console

Is there a built-in binary search tree in .NET 4.0, or do I need to build this abstract data type from scratch?

# Edit

This is about the binary search tree specifically, and not abstract data type &quot;trees&quot; in general.

Is there a built-in Binary Search Tree in .NET 4.0?

I understand the reasons why one can&#39;t just do this (rebalancing and stuff):


    iterator i = m.find(33);
    
    if (i != m.end())
      i-&gt;first = 22;


But so far the only way (I know about) to change the key is to remove the node from the tree alltogether and then insert the value back with a different key:

    iterator i = m.find(33);
    
    if (i != m.end())
    {
      value = i-&gt;second;
      m.erase(i);
      m[22] = value;
    }

This seems rather inefficient to me for more reasons:

1. Traverses the tree three times (+ balance) instead of twice (+ balance)

2. One more unnecessary copy of the value

3. Unnecessary deallocation and then re-allocation of a node inside of the tree

I find the allocation and deallocation to be the worst from those three. Am I missing something or is there a more efficient way to do that?

I think, in theory, it should be possible, so I don&#39;t think changing for a different data structure is justified. Here is the pseudo algorithm I have in mind:

1. Find the node in the tree whose key I want to change.

2. Detach if from the tree (don&#39;t deallocate)

3. Rebalance

4. Change the key inside the detached node

5. Insert the node back into the tree

6. Rebalance






What is the fastest way to change a key of an element inside std::map

I&#39;m building a symbol table for a project I&#39;m working on. I was wondering what peoples opinions are on the advantages and disadvantages of the various methods available for storing and creating a symbol table.

I&#39;ve done a fair bit of searching and the most commonly recommended are binary trees or linked lists or hash tables. What are the advantages and or disadvantages of all of the above? (working in c++)

Binary Trees vs. Linked Lists vs. Hash Tables

I know that performance never is black and white, often one implementation is faster in case X and slower in case Y, etc. but in general - are B-trees faster then AVL or RedBlack-Trees? They are considerably more complex to implement then AVL trees (and maybe even RedBlack-trees?), but are they *faster* (does their complexity pay off) ?

**Edit:** I should also like to add that if they are faster then the equivalent AVL/RedBlack tree (in terms of nodes/content) - *why* are they faster?

B-tree faster than AVL or RedBlack-Tree?

What is the algorithm for doing a post order traversal of a binary tree **WITHOUT** using recursion?


Post order traversal of binary tree without recursion

I&#39;m looking for the best way to calculate a nodes balance in an [AVL-tree][1]. I thought I had it working, but after some heavy inserting/updating I can see that it&#39;s not working correct (at all). 

This is kind of a two-part question, the first part would be how to calculate the height of a sub-tree, I know the definition *&quot;The height of a node is the length of the longest downward path to a leaf from that node.&quot;* and I understand it, but I fail at implementing it. And to confuse me further this quote can be found on wikipedia on tree-heights *&quot;Conventionally, the value -1 corresponds to a subtree with no nodes, whereas zero corresponds to a subtree with one node.&quot;*

And the second part is getting the balance factor of a sub-tree in an AVL tree, I&#39;ve got no problem understanding the concept, *&quot;get the height of your `L` and `R` sub-trees and subtract `R` from `L`&quot;*. And this is defined as something like this: `BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]`

Reading on wikipedia says this on the first few lines describing insertions into an AVL tree: *&quot;If the balance factor becomes -1, 0, or 1 then the tree is still in AVL form, and no rotations are necessary.&quot;*

It then goes on, saying this *&quot;If the balance factor becomes 2 or -2 then the tree rooted at this node is unbalanced, and a tree rotation is needed. At most a single or double rotation will be needed to balance the tree.&quot;* - which I have no trouble grasping. 

But (yes, there&#39;s always a but).

Here&#39;s where it gets confusing, the text states *&quot;If the balance factor of R is 1, it means the insertion occurred on the (external) right side of that node and a left rotation is needed&quot;*. But from m understanding the text said (as I quoted) that if the balance factor was within `[-1, 1]` then there was no need for balancing? 

I feel I&#39;m so close to grasping the concept, I&#39;ve gotten the tree rotations down, implemented a normal binary search tree, and on the brink of grasping AVL-trees but just seem to be missing that essential epiphany.

**Edit:** Code examples are preferred over academic formulas as I&#39;ve always had an easier time grasping something in code, but any help is greatly appreciated.

**Edit:** I wish I could mark all answers as &quot;accepted&quot;, but for me NIck&#39;s answer was the first that made me go &quot;aha&quot;.


  [1]: http://en.wikipedia.org/wiki/AVL_tree

The best way to calculate the height in a binary search tree? (balancing an AVL-tree)

What is the basic algorithm for testing if a tree is symmetrical?  Because it is a binary tree, I would assume that it would be a recursive definition of sorts

The formal question is below:


A binary tree is a mirror image of itself if its left and right subtrees are identical mirror images i.e., the binary tree is symmetrical.
This is best explained with a few examples.

      1
     / \
    2   2

TRUE

       1
      / \
     2   2
      \
       3

FALSE

         1
       /   \
      2     2
     / \   / \
    4   3 3   4

TRUE

           1
         /   \
        2     2 
       / \   / \
      3   4 3   4

FALSE

           1
         /   \
        2     2
       /       \
      3         3

TRUE

In a programming language of choice, define a BTree class/C struct and an associated method to check if the tree is a mirror image. For statically typed languages, you can assume that node values are all integers.

    Class/structure definition
    BTree {
      BTree left;
      BTree right;
      int value;
    }

Assume that the root of the tree is tracked by caller and function isMirror() is invoked on it.

Also, if defining a class, make sure to provide a no-argument constructor and getter/setter methods if data elements are not publicly accessible.

Check if a binary tree is a mirror image or symmetric

I&#39;ve seen binary trees and binary searching mentioned in several books I&#39;ve read lately, but as I&#39;m still at the beginning of my studies in Computer Science, I&#39;ve yet to take a class that&#39;s really dealt with algorithms and data structures in a serious way.

I&#39;ve checked around the typical sources (Wikipedia, Google) and most descriptions of the usefulness and implementation of (in particular) Red-Black trees have come off as dense and difficult to understand. I&#39;m sure for someone with the necessary background, it makes perfect sense, but at the moment it reads like a foreign language almost.

So what makes binary trees useful in some of the common tasks you find yourself doing while programming? Beyond that, which trees do you prefer to use (please include a sample implementation) and why?

All Binary Tree Solutions on Gang of Coders

Total of 24 Binary Tree Solutions