Talk:Binary tree

level vs breadth first

Isn't level and breadth search the same? (http://tekpool.wordpress.com/2006/11/04/binary-tree-traversal-breadth-first-aka-width-first-aka-level-order/) ¼

tree

There is nothing here on, "Strong Binary Trees", they are used in things like Astronomy for multiple star systems. http://mathworld.wolfram.com/StronglyBinaryTree.html —Preceding unsigned comment added by 91.51.125.15 (talk) 19:20, 24 October 2008 (UTC)

I don't see anything in the definition of "Strong Binary Trees" that distinguishes the concept from a "full binary tree", etc.

---

Under "types" of binary trees, I think it would be appropriate to add "extended binary tree" (http://mathworld.wolfram.com/ExtendedBinaryTree.html) --Hughitt1 02:31, 4 April 2006 (UTC)

---

let T be binary tree with height h and n nodes show that log(n+1)-1<=h<=(n-1)/2 for which values of n and h can be above lower upper bounds of h be attained equally

---

The article says:

Graph theorists use the following definition. A binary tree is a connected acyclic graph such that the degree of each vertex is no more than 3.

This appears to be incorrect. Consider the graph with four vertices A, B, C, and X, where X is attached to A, B, and C. This is a connected acyclic graph where every vertex has degree no more than 3, but it is not a binary tree.

I believe that the definition of a binary tree in graph-theoretic terms will require that the graph be a directed acyclic graph. Then we might require that every node have outdegree at most 2, that the root node have indegree 0, and that every other node have indegree 1.

Dominus 14:40, 17 Feb 2004 (UTC)

I think the current definition is actually correct. A binary tree does not require each node to have either zero or two children, so simply choose some node with degree <= 2 as the root (which must exist; in fact we must have a vertex of degree 1) and then assign all adjacent nodes not yet assigned as its children. Repeat this for each new node added, and you establish all parent-child relationships. The directed interpretation is convenient, but less general, because it fixes the root. This might deserve mention in the article.

As for X,A,B,C, you can follow the above procedure, assigning A as the root, X as its unique child, and B,C as the children of X.

Derrick Coetzee 04:26, 18 Feb 2004 (UTC)

Perhaps, but I don't think anyone ever does define it that way. You could also define a binary tree geometrically, in terms of line segments in the cartesian plane, but nobody does that either. Is there a source for this definition? Or is it just the product of some wikipedian's imagination? Dominus 16:34, 18 Feb 2004 (UTC)

In a few books I have handy, binary trees are defined with respect to a particular root node. One defines it as either being empty or being partitioned into a root node, a left subtree, and a right subtree. Another defines it as a rooted tree where each node has at most two children, where a rooted tree is defined by the procedure I gave above. I imagine some source might use the definition in the article, but you're right that in general most people think of a binary tree as having a specific root and a specific order on children.

Derrick Coetzee 15:20, 20 Feb 2004 (UTC)

I also don't see the point of defining a binary tree as an undirected graph, since you're going to have to infer directions on it anyway.

Also, a question: can a binary tree have a right child and no left child? I came to this article to look that up, and the article doesn't make it clear.

RSpeer 22:27, Mar 12, 2005 (UTC)

I have seen this definition used in graph theory books. I can get a real reference. The only other definition I've seen is a recursive one: a binary tree is either a vertex or a vertex with two edges going out to binary trees. I'll throw this in. Deco 23:51, 12 Mar 2005 (UTC)

A node can have zero, one (either side), or two children. Also, the definition about no node having degree greater than three is correct, as long as one restriction is placed: the number of nodes with degree three is exactly two less than the number of nodes of degree three. Lastly, binary trees are not ordered; binary search trees are. I corrected the article on that point.

Dominus, your counterexample does not prove anything; choose any node except X as root, and no conflict exists.

You may be misunderstanding the meaning of "ordered" in this context. This simply means that there are distinguishable left and right children, not that the elements are ordered. Binary trees need not be ordered trees, I suppose, but in nearly all implementations a left-right child order is naturally imposed, largely because unordered lists (sets) aren't a common language feature. There are of course many applications where this order is irrelevent, like binary heaps. Deco 07:09, 7 May 2005 (UTC)

duplicates

As far as I know, duplicates are allowed in binary trees. Should this be added to the article, or is it even relevant? Meonkeys 18:47, May 16, 2005 (UTC)

RSPeer: yes, a binary tree can have a right child and no left child. Node "5" in Image:Binary_tree.png has a right child and no left child. Meonkeys

Hmm, duplicates allowed. That would be good to mention - really I should have had duplicates in the diagram. I'll fix this sometime. Please be bold. Deco 08:50, 19 May 2005 (UTC)

Counting binary trees

Should we also include the formula for counting binary trees somewhere? This is used when you want to do stastical analysis of insertion and deletion of nodes in the tree.

Somehow I think the formula $k={\frac {1}{2n+1}}{2n+1 \choose n}$ should be mentioned somewhere. Preferably with a reference to where the formula is derived. In the formula, k is the number of trees that has exactly n nodes. So for example there are 5 binary trees with 3 nodes. This is also related to the fact that you can write three parenthesis in 5 different ways on a line: ((())), (()()), (())(), ()(()), ()()().

Of course, imposing further structure on the tree (Red black trees, AVL trees etc) would also influence the likelyhood of a given tree appearing and prohibit some. Speaking of variants, we should perhaps add a little reference to red black trees, avl trees and n-ary trees (binary trees is a special case where n=2), as well as many other trees that are used as ways of structuring data.

salte 12:54, 14 December 2006 (UTC)

Examples

The article so far seems to be only a discussion of implementation methods and operating rules. I have noticed no mention of advantages/disadvantages of using binary trees over more conventional programming structures. Also, can someone provide some real world applications where a binary tree could be used to solve a problem more easily or efficiently than other methods?

• Binary trees are superior to for example linked lists to hold a collection of items. Also, because they are binary you generally have few tests before determining where to go after visiting a given node. For example if you visit a node A and you have determined that this is not the node you are looking for, you also often typically know if you should check the left or the right branch after when searching for a node. Looking through a set of n nodes will take an order of O(log(n)) time while in a linked list it is of the order O(n) and as log(n) < n (base is larger than 1) and for large n the difference is large you can gain much speed. For example I once had a program that used a linked list and it took a long time to run, I then aborted it after an hour when it was still not done, rewrote to use a binary tree and the program took 8 minutes to run before it completed. For example in C if you use strcmp(skey,nkey) to compare the search key with the node key you first check if the return value was 0 - if it was 0 it means the keys were equal and you have found the node, if the return value was negative it means the node key was later in the sort and so you check out the left branch. Thus, all the nodes on the right branch are already known to be too large and can be skipped in the search. If the return value was positive you know you can skip the left branch and only check the right branch for the same reason.

salte 14:12, 3 April 2007 (UTC)

the degree of a node in a rooted tree

the degree of a node in a rooted tree is the number of children - the edge from its parent node does not count. Charieshane 04:00, 7 March 2007 (UTC)

It sounds like you're talking about the out-degree (considering the tree to be a directed graph). Your definition would be inconsistent with the definition of degree for graphs in general.

Now, in applied contexts like computer science, the out-degree is the useful measure, and it can be referred to as just the "degree". But I think the only place the degree is mentioned in the article is the formal graph theory definition, so it should stay consistent with graph theory.

rspeer / ɹəədsɹ 08:19, 7 March 2007 (UTC)

car, cdr, and lots of parens?

Could this article be amended to mention that trees may be encoded as strings, by using parenthesis? In mathematics, binary trees are known as free magmas, and the encoding as a string is important for algebra e.g. for free objects, and also for the foundations of syntax. The string encoding is also used by lisp (programming language), scheme (programming language) and prolog. Should also mention that the standard names for navigating a binary tree are CAR and CDR. Also, the encoding at the bottom of the article is wrong; the internal node labels (cons) were left out.linas 02:37, 9 April 2007 (UTC)

Encoding n-ary trees as binary trees

The diagram in this section is confusing because there are two distinct nodes labeled "G". Muddle-headed Wombat 18:04, 9 April 2007 (UTC)

The Line between M and N should be blue 77.56.110.121 (talk) 15:57, 26 March 2008 (UTC)

Nodes/Vertices

Is there a difference between the node of a graph and the vertices of a graph? If not, wouldn't it be better to use just a single word throughout the article? Taemyr 19:49, 12 May 2007 (UTC)

special cases of depth-first traversal

I think there is something wrong to say Pre-order, in-order, and post-order traversal are all special cases of this(depth-first traversal)

In-order and post-order traversals visit child nodes before visiting their parents, which breaks the caveat that it must be a child of a node we have already visited. --71.159.61.221 03:00, 28 June 2007 (UTC)

Lisp-style structures are not binary trees

A lisp-style node can point to left and right nodes, but if it does then the node cannot store a value. This makes it fundamentally different to a binary tree (assuming a binary tree node must be able to store a value). If so, then should the "encoding n-ary trees" section be moved/removed?

Also, the "combinatorics" section mentions "car" and "cdr" and talks about trees as (a b) where a and b are subtrees but not, say, (a x b) where x is the node value. --2007-07-20

Actually cons-based data structures are binary trees, but they can only store data in leaves. Conventionally they almost always store data in each cons's left child and sublists in each cons's right child (which makes the tree a degenerate list). You can represent arbitrary trees as well: for example, using dotted cons notation, (((1 . 2) . 3) . (4 . 5)) could be a valid binary tree storing some numbers. This is somewhat uncommon but is used. Dcoetzee 08:20, 21 July 2007 (UTC)

Graph

This is not true at all. Duplicates were included to illustrate that a general labelled binary tree can include duplicate labels, and they were placed out of order to illustrate that generally they don't require order. Dcoetzee 19:45, 10 August 2007 (UTC)

Definition in graph theory: glitch?

The current definition,

Another way of defining binary trees is a recursive definition on directed graphs. A binary tree is either:

• A single vertex.
• A graph formed by taking two binary trees, adding a vertex, and adding an edge directed from the new vertex to the root of each binary tree.

makes the tree

  A
 /
B

an invalid binary tree, as it cannot be formed by combining two smaller binary trees. Does anyone have a more correct definition than this? Zetawoof_(ζ) 00:01, 17 September 2007 (UTC)

The definition depends on whether or not you consider the leaves to contain values, or whether they're "null" leaves. The current definition is correct in the latter case, while to permit the definition you'd need something more complicated that's difficult to describe with a recursive definition. I prefer the more structural definition that it's just a directed acyclic graph of maximum degree 3. Dcoetzee 02:43, 17 September 2007 (UTC)

Heaps?

Maybe we should mention that a complete binary tree is often referred to as a heap in computer science. This seems relevant to me as the opening statement refers to computer science. Though somewhat irrelevant it might also be useful to mention that complete trees can be implemented using an array as opposed to a linked structure which is mentioned in the other sections. Only in the array implementation a parent n can reach it's children at with something like left = 2n + 1 and right = 2n + 2, assuming a 0 indexed array. —Preceding unsigned comment added by Cldoyle (talk • contribs) 02:04, 12 January 2008 (UTC)

Binary heaps are mentioned (and linked) in the introduction. Do note that a complete binary tree is not the same thing as a heap! The binary tree property (left < parent < right) is quite different from the heap property (parent < child). Zetawoof_(ζ) 06:28, 12 January 2008 (UTC)

I completely agree with you,Zetawoof! Visame (talk) 17:35, 18 May 2008 (UTC)

Repeated Definitions

There are two definitions for almost complete binary trees which pretty much state the same thing. Should these be merged or should one be deleted? I think the lower one more clearly represents an almost complete binary tree. —Preceding unsigned comment added by 99.225.178.225 (talk) 14:22, 14 April 2008 (UTC)

Many things wrong

Before you think me a crazy ranter, I have a Masters degree in the field and have taught data structures at the University of Virginia and done research in graph theory.

Now the non-crazy rant.

• First, a binary tree is a graph from theoretical computer science. IT IS NOT A "TREE DATA STRUCTURE".
• The first node is the "root". The "parent" is the unique node that points to a node. (Sentence 2)
• Type theory should not be in the first paragraph.
• Binary trees don't need directed edges. They're trees!
• It should be said that the only tree without a root node is the empty tree.
• The definition of height does not give a height for an empty tree. A tree with 1 node has a height of 1. The root should have depth 1.
• The definition of ancestor is wrong. Node p must be ON THE PATH from the q to the root.
• I have never heard of the "size of a node". It is the "size of a subtree rooted at a node".
• The in-degree is always 1, except for the root. That defines a tree. You don't need that definition here.
• The out-degree is not important here either, except to say at the top that a node has at most 2 children.
• Delete "rooted binary tree". Leave that for the graph theory section.
• I SEVERELY DOUBT that a "infinite complete binary tree" as defined has AlephNull nodes. It's a power set of AlephNull levels.
• Can a "balanced binary tree" have a non-leaf with only one child? Doesn't a balanced binary tree have to be full? Also, by this definition, a red-black tree is not balanced, since it's leafs different in height by log(n)
• "A rooted tree has top node as root." - Why is this here?

Please check this list and fix things. If you change your definition of height so that an empty tree has height 0, you will have to change your formulae for nodes-per-height.

Well, I can address one of your concerns.

• _The_ infinite complete binary tree has AlephNull nodes.
• All infinite complete binary trees have AlephNull levels.
• If Countable Choice on Finite Sets, then all infinite complete binary trees are isomorphic, and so have AlephNull nodes.

JumpDiscont (talk) 06:39, 19 October 2009 (UTC)

No, I do not think you are crazy at all. Actually the article's main definition is wrong: "a binary tree is a tree data structure in which each node has at most two children". No! that does not get the main point of binary trees, where there is always a left and a right side, even if there is only a single child. Better: a binary tree is a hierarchical structure which is either empty, or consists of a node and two binary trees, called the left and right child of that node. If you do not believe me, read TACP by D. Knuth. Binary tree are not a special case of trees, they are a species of their own. Also the graph theoretical definition is not very much to the point: does it really capture the left/right issue? Jochgem (talk) 12:13, 6 November 2009 (UTC)

As a practicing engineer, I find a few aspects of the article confusing. The biggest is the constant talk of rooted trees. What the heck is a non-rooted tree??? I have never heard of this and think that any attempt to look at a tree as a graph subset would be confusing, misleading, and most likely useless for understanding the basic data structure. Unless there is a meaningful concept of non-rooted trees that I somehow missed, that would make rooted binary trees a more obnoxious version of the classic "hot water heater" grammatical problem. Also, I think that at the very least, binary search trees should be included in the sub tree types. It and a few other types of trees are far more relevant than some of the ones listed now. —Preceding unsigned comment added by 67.183.113.131 (talk) 03:39, 16 July 2010 (UTC)

height instead depth

Types of binary trees .... A balanced binary tree is where the depth of all the leaves differs by at most 1. Balanced trees have a predictable depth ...

It shoukd be Balanced trees have a predictable height —Preceding unsigned comment added by 83.43.153.47 (talk) 08:20, 29 November 2009 (UTC)

I'm Mdnahas, the author of "Many Things Wrong". I've split the article up into 3 articles, "Binary Tree", "Binary Tree (data structure)" and "Binary Tree (graph theory)". Cluebot seemed to dislike my change to Binary Tree, since it didn't realize the deletion of 15000 chars was actually a move of them into a different linked article.

Anyway, I undid the Cluebot revert. If anyone has power over Cluebot and agrees with my change, please help me fight it. (FYI, I know I'm a newbie here in how to edit these pages, but I'm an expert in the field.) —Preceding unsigned comment added by Mdnahas (talk • contribs) 15:07, 31 December 2009 (UTC)

Delete this if I'm silly, but...

Isn't the classical graph, pictured here, incorrect on the Binary tree article?

Explanation

The node labeled "2" (assumed to be a value of the node) has a greater value linked on the left, and a lesser value linked on the right.

However, the node labeled "7" has a lesser value (than 7) on the left, and a greater value on the right.

I looked up the Binary tree article to link from an article of mine on binary tree signatures which is proposing a project to detect randomness perturbed by determinant effects on randomness, as some algorithmically detectable deviation across multiple trees. (This paragraph is a shameless plug I suppose. Contact me if interested in a joint paper.)

Hopefully I'm not totally mistaken about the incorrect graphic, and do as you will with my scratches here... Regards -DonEMitchell (computer programmer)

I think you are thinking of binary search tree. I agree that more emphasis should be given to this (although there is a small link at the top). —Preceding unsigned comment added by 67.183.113.131 (talk) 03:42, 16 July 2010 (UTC)

Balanced binary tree properties

This cant be right : # A balanced binary tree is where the depth of all the leaves differs by at most 1. Balanced trees have a predictable depth (how many nodes are traversed from the root to a leaf, root counting as node 0 and subsequent as 1, 2, ..., depth). This depth is equal to the integer part of log2(n) where n is the number of nodes on the balanced tree. Example 1: balanced tree with 1 node, log2(1) = 0 (depth = 0). Example 2: balanced tree with 3 nodes, log2(3) = 1.59 (depth=1). Example 3: balanced tree with 5 nodes, log2(5) = 2.32 (depth of tree is 2 nodes).

Here is counter example , n=7 , Node1 has left child Node2 and right child Node3 , Node2 has only one left child Node4, Node3 has left child Node5 and right child Node6 ,Node5 has only one left child Node7, so we have 7 nodes. This tree is balanced ,right ? Article suggests it should have log2(7)=2.807 , or 2 as it depth, but we can see that its depth is 3 . What gives ? —Preceding unsigned comment added by 68.46.189.142 (talk) 04:40, 22 January 2010 (UTC)

I suspect the definition of balanced given on the current article is not correct. Here is one article that gives a tree that is unbalanced by a different definition, but balanced by this one. http://www.gamedev.net/reference/articles/article1433.asp — Preceding unsigned comment added by Pohl (talk • contribs) 14:13, 15 December 2010 (UTC)

Let me elaborate. I think the biggest reason to suspect that this definition is not accurate is that the definition is not recursive. Take, for example, the following case:

                            A
                             \
                              B
                               \
                                C
                                 \
                                  D
                                   \
                                    E
                                     \
                                      F
                                       \
                                        G
                                       / \
                                      H   I
                                     /     \
                                    J       K

This is a tree "where the depth of all the leaves differs by at most 1", because this tree has exactly two leaves (J and K) and they have the same depth. However this tree is not balanced in any useful sense that might be leveraged by splay trees or AVL trees. The definition that I am more familiar with is "A binary tree is balanced if and only if at every node the difference in heights of subtrees is no greater than one." Note that under this definition, the current main illustration of this article is not balanced, in contradiction to its current caption. (The root node's right child "5" has a left subtree of height 0, and a right subtree of height 2.) The only citation that I can offer for this definition is Duane A. Bailey's "Java Structures: Data Structures in Java for the Principled Programmer", which is far from definitive, but since the article's current definition comes with no citation whatsoever, perhaps this is sufficient reason to change the article. http://www.cs.williams.edu/JavaStructures/Welcome.html

Ok, I found another source with a similar definition of a balanced binary tree: "A balanced binary tree is a binary tree in which the heights of the two subtrees of every node never differ by more than 1." -- Data Structures Using C (Aaron M. Tenenbaum, Yedidyah Langsam, and Moshe J. Augenstein) Prentice Hall, 1990 page 398. This supports the notion that the definition should be in recursive terms. If there's no objection I'll update the entry accordingly in the next few days. — Preceding unsigned comment added by Pohl (talk • contribs) 01:18, 19 December 2010 (UTC)

As for the illustration at the top of the article, let's apply the recursive definition and label the differences in the heights of the left & right subtrees at each node:

                     0
                    / \
                   /   \
                  /     \
                -1      -2
                / \       \
               /   \       \ 
              0     0       1
                   / \     / 
                  0   0   0  
     
      

Notice the node labled with a negative 2. This demonstrates that this tree is not balanced by the recursive definition. — Preceding unsigned comment added by Pohl (talk • contribs) 18:19, 19 December 2010 (UTC)

depth/height and broken external link

The article says "A (rooted) tree with only one node (the root) has a height of zero (or one[2]).", and similarly for the depth. Is this "or one" really correct? The linked external article doesn't mention neither depth nor height. Since I don't know this topic, I will not do the correction myself. --HelgeStenstrom (talk) 12:14, 1 November 2010 (UTC)

Merge discussion

I propose that whatever is of value in Deletion in binary tree should be merged with this article. Malleus Fatuorum 17:05, 26 November 2010 (UTC)

Does the lack of feedback indicate agreement or apathy? Malleus Fatuorum 16:31, 12 December 2010 (UTC)

I agree. marksoe —Preceding unsigned comment added by 150.156.195.42 (talk) 23:53, 16 December 2010 (UTC)

I agree. The deletion page is incomplete, filled with spelling errors, and hard to follow. Chris857 (talk) 22:33, 17 December 2010 (UTC)

I added a section in Binary Tree for node deletion that includes most of the information in the article. Do we want to keep the block of code from Deletion in binary tree or just scrap the page? I found that the page in question also has at least one inaccuracy, "a binary tree is always sorted..." Chris857 (talk) 23:10, 17 December 2010 (UTC)

I'd vote for scrapping the page. Malleus Fatuorum 23:31, 17 December 2010 (UTC)

It's gone, with a redirect to Binary tree#Deletion. Chris857 (talk) 00:14, 18 December 2010 (UTC)

Deletion of a node with two children

Is it possible to delete a node from a binary tree that has two children? I know that its children can't just be assigned to its parent, because then the tree would be ternary. I've seen that it is possible with a binary search tree. [1] Chris857 (talk) 04:13, 19 December 2010 (UTC)

Removed redundant paragraph from section Ahnentafel list

I have been bold and removed a paragraph from Binary tree#Ahnentafel list. I'll paste it here: "A binary tree can also be represented in the form of array as well as adjacency linked list. In the case of array, each node(root,left,right) is simply placed in the index and there is no connection mentioned about the relationship between parents and children. However, in linked list representation we can find the relationship between parent and children. In array representation the nodes are accessed by calculating the index. This method is used in languages like FORTRAN which doesn't have dynamic memory allocation. We can't insert a new node into array implemented binary tree with ease, but this is easily done when using a binary tree implemented as linked list."

The reason for removal is that the information in it is already stated in the first paragraph and in a better way. If anyone disagrees, discuss. Silver hr (talk) 21:33, 27 January 2011 (UTC)

So, i have a few questions.. if you please. 1.Who was the first to use binary trees? 2.why are binary trees are drawn from the top down.??

thanks in advance.