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/) ¼

-- Yes, they are the same. We should not be discussing traversal inside Binary tree but instead just point to the Tree traversal article. -- Ryuunoshounen (talk) 18:39, 29 November 2013 (UTC)

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)

I would think that depth and height are different things, depth meaning a node's traversal distance from a given parent node.

This way, an empty tree has height 0 with no nodes to speak of for depth. A tree with a single root node is height 1, root has depth 0 (no parent / no distance from root). 3 node tree has height 2 and bottom nodes have depth 1 from root, etc.

67.182.168.147 (talk) 05:09, 28 November 2013 (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)

Are we caring about advanced degrees? I have a PhD in computer science, and I strongly AGREE with OP that empty tree has height of zero. I further strongly agree that the main definition should be "A binary tree is either empty, or a node containing exactly two binary trees". Knuth is a good reference, so is How To Design Programs. What's the procedure for fixing this? Just go and make the change and then let people argue about it? This change will touch many parts of the page. Clements (talk) 18:48, 14 April 2017 (UTC)

Self-edit: It's been pointed out to me that NIST disagrees with me, and specifies that Node(16,Null,Null) has height zero. I think this is a deeply unfortunate choice, as it reinforces the notion that Null is not a tree, but this definition is widely accepted, and much more clearly stated by the NIST than it is by Knuth. Clements (talk) 03:35, 11 May 2017 (UTC)

References

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. —Preceding unsigned comment added by 85.65.108.106 (talk) 10:47, 5 March 2011 (UTC)

Removed two sentences from section "Types of Binary Trees"

• There was a link to the Tango tree article, but this section is not about algorithmic developments; this would be more appropriate in the template.
• there was a repetition here of Strictly Binary Tree, which was already defined earlier in the list.

LandruBek (talk) 19:42, 28 June 2011 (UTC)

Info box

Shouldn't this article have one of those info boxes summarizing the time complexity of insert/remove/lookup operations?

See http://wiki.alquds.edu/?query=AVL_tree

Dj0nes (talk) 17:19, 6 January 2012 (UTC)

Need to separate graph theory from the data structure

This page has a mixture of content. Some is about the data structure and some is about the mathematical properties of that data structure. I believe a lot of the math should be split into a separate page and connected to graph theory. (FYI, I've both taught data structures and done research in graph theory.)

Apparently I tried this once upon a time, and it got rolled back. Checkout the change by mdnahas on 2009-12-30T22:24:21+00:00 — Preceding unsigned comment added by Mdnahas (talk • contribs) 21:40, 15 February 2013 (UTC)

Confusion galore

I am admittedly not the first one to notice this, but the definitions on this page are still seriously confusing, undeservedly for such a basic and simple notion as that of binary trees. I suggest reorganizing it by putting the binary-trees-as-inductive-type definition first (i.e., a binary tree is either the empty binary tree, or a pair of binary trees; a labelled binary tree is either the empty labelled binary tree, or a pair of labelled binary trees plus a label), with some examples and illustrations (a realization as bracketings for those unhappy with inductive definitions); and only then any relations with graph theory and data structures. The reason for this is that the inductive-type definition is the only one which can be taken at face value without additional clarifications or modifications:

• Defining a binary tree is a "data structure" feels like putting the cart before the horse, as binary trees are a simple mathematical notion, while "data structure" is a somewhat vague computing term and "abstract data type" has a rather complex definition.
• Claiming that a binary tree is a "tree data structure" is misleading for reasons that have already been named: Nodes in binary tree know their left and right children even if these are their only children; this is not provided for in the definition of Tree (data structure), and tweaking that definition for the purpose of binary trees feels hacky and overcomplicated.
• Defining a binary tree as a certain kind of graph is wrong; again, no standard structure in graph theory can encode the left-ness or right-ness of a single child.

It is perfectly fine for all these connections to be mentioned, but the definition should be simple and free from haze and ambiguities. -- Darij (talk) 05:30, 27 March 2014 (UTC)

I very much agree with your first two points (not in the bullets), that the recursive def is the real def used (as Aho notes not quite equivalent with what you get from graph theory). I've found a source to say the obvious thing that binary trees as used in CS are normally labeled, so I've added that. I've also fixed the recursive def section cause it was obviously wrong. But I'm not sure how to put it in the lead without making it too laborious. I'm not happy with the current 1st paragraph of lead because it relies on the notion implicitly defined in tree (data structure) for rooting & recursion. As for your bullet points, the waters are muddy in CS, so I'm not sure you can actually separate some kind of abstract concept from the data structure that cleanly. Your final bullet point was absolutely correct, but I had helluva time finding a ref to support it. Besides Aho et al. most textbooks don't mention it. JMP EAX (talk) 20:41, 27 July 2014 (UTC)

Thank you for the feedback! As for actually fixing the mess, I fear I am just as much at a loss as you are. I feel that it would be helpful (as the first step!) to completely remove every mention of graphs from the article (and this includes graph-theoretical trees), keeping only the compsci definition of a "planar" (i.e., knowing left and right) labelled binary tree around. Then, step by step, we could add equivalent definitions (labelled Dyck words), variations (unlabelled, un-planar, un-rooted) and connections to graph theory. The problem is that there is too much CS stuff in the article I don't know what to do with (and people will likely want it in), and also I have a rather meager leeway of time these days. If you want a reference which (I think) does binary trees right, see Stanley's EC1: http://math.mit.edu/~rstan/ec/ec1/ there the Appendix. (Despite the Appendix being about graph theory, Stanley does not view trees as graphs. This has to say something!)

Darij (talk) 21:33, 27 July 2014 (UTC)

I've managed to find (and I have added to the article) one def in terms of graph theory that is not wrong (by Flum and Grothe); "not wrong" as in matches the concept from the recursive def found in most CS textbooks, but it's as I suspected rather laborious. Still need to intro the typical math terms and concept of "weakly binary tree" as mathworld calls it, (following Finch's Mathematical Constants) even though that notion doesn't actually tell apart nodes with a single left/right child. But it's what the combinatorics/math guys studied... JMP EAX (talk) 03:27, 28 July 2014 (UTC)

Stanley, like many mathematicians, gives a recursive definition for k-ary tree, but then defines binary tree as 2-ary tree, so it's not the common CS concept of binary tree he is defining. 188.27.81.64 (talk) 17:06, 29 July 2014 (UTC)

Actually, I missed something in Stanley; on the previous page he defines a "tree (or rooted tree)" to actually be a trie (i.e. has partitioned children), even though he puts this def under "graph theory concepts", an area in which his def of tree is way non-standard. He has some graphical examples where a 3-ary tree with middle but no left child is different from one with right but no middle and left child. So his binary tree is the CS one as a result of particularizing this notion of tree. 188.27.81.64 (talk) 17:24, 29 July 2014 (UTC)

Looking at it more carefully, Stanley's def of tree is actually rather faulty, because it's infinite:

“ A tree (or rooted tree) T is a finite set of vertices such that:

a. One specially designated vertex is called the root of T , and b. The remaining vertices (excluding the root) are partitioned into m ≥ 0 disjoint nonempty sets T1, . . . ,Tm, each of which is a tree. The trees T1, . . . ,Tm are called subtrees of the root.

”

The problem is that subtrees must all be "nonempty" in his def, so his trees must be infinite according to this def, which is not matching the examples he then gives. I see his book has long errata, so maybe he fixed that def. It's also not clear if m is chosen for each subtree or only once globally, i.e. if it quantifier is nested or not; these two cases result in different definitions, of course. I think Stanley is better avoided as source for now. 188.27.81.64 (talk) 17:40, 29 July 2014 (UTC)

Thank you, 188.27.81.64, for spotting this error! I have notified Stanley about it. -- Darij (talk) 20:56, 30 July 2014 (UTC)

The Springer/Soviet EOM, while disappointingly not giving a formal definition (it gives one in words that's rather muddy) does give a pictorial example where {{},{foo},{{},{bar},{}}} is different from {{{},{bar},{}},{foo},{}} and they stress this difference. [2] 188.27.81.64 (talk) 17:09, 29 July 2014 (UTC)

rooted binary tree

The definition seems to be that of a non-empty binary tree, so - if so - why not just say so? 68.183.92.186 (talk) 21:51, 13 May 2014 (UTC)

The catch is that rooted binary tree, which even had its own little (but very confusing) article until recently, is often not defined the by people that use the phrase and they don't bother to define some (unrooted) binary tree either. The few (reputable) sources that do define it, define it the same way as binary tree, e.g. [3]. I did find one source explicitly saying these are normally the same concept, so I've added that. JMP EAX (talk) 20:57, 27 July 2014 (UTC)

Removed the Berman & Paul ref

It's actually a really confusingly written book, as far as binary trees are concerned. I'm not surprised that whoever used that as ref was unable to write a correct recursive definition of binary trees. Here's what the book has as def:

DEFINITION 4.1.1 A binary tree T consists of a set of nodes that is either empty or has the following properties:

1. One of the nodes, say R, is designated the root node.
2. The remaining nodes (if any) are partitioned into two disjoint subsets, called the left subtree and the right subtree, respectively, each of which is a binary tree.

It's hard to think of a more unclear way to say that. It's clear that whoever red that got confused into (recursively) defining binary tree as just full binary tree did so because he missed the empty set being binary tree, which is actually one of the recursion branches in the above def despite not being numbered, while the "1"-numbered clause there is just a red herring as far as the recursion is concerned. JMP EAX (talk) 03:35, 26 July 2014 (UTC)

Aho et al.'s observation

The obvious thing that's needed to make that formal is a partial mapping from left/right labels to outgoing edges from each node, but I wasn't able find a single source to say that explicitly. JMP EAX (talk)

Here's a mathematician who almost managed to give a working definition in terms of graph theory. Anany Levitin's (he is actually a math guy transplanted to CS) "Introduction to the Design and Analysis of Algorithms" 3rd ed., p.33: "A binary tree can be defined as an ordered tree [which is defined as rooted] in which every vertex has no more than two children and each child is designated as either a left child or a right child of its parent; a binary tree may also be empty." But that doesn't prevent you from labeling both children of a node as "left". Which is why you need a partial function. JMP EAX (talk) 01:58, 28 July 2014 (UTC)

Full binary tree etc.

The def of "full" binary tree here doesn't match the common one in most textbooks, which define full as all leaves being on the same level. That section and the terminology throughout the article needs a fair bit of rework. JMP EAX (talk) 03:18, 28 July 2014 (UTC)

I think NIST notes that discrepancy in definitions in other texts that they found and it is probably better to follow NIST. 135.180.116.147 (talk) 15:50, 19 August 2020 (UTC)

Truly awful writing

If the goal of this article was to hide an essentially simple subject behind a cloud of confusing waffle then it has succeeded brilliantly. In my opinion the introductory paragraph beginning "from a graph theory perspective..." could be deleted entirely and it wouldn't subtract an iota from the useful content of the article. I mean, waffling on about the original meaning of terms I never even heard of in 30 years as a programmer... why? — Preceding unsigned comment added by 82.68.15.142 (talk) 14:52, 12 September 2014 (UTC)

Thank you for your suggestion. When you believe an article needs improvement, please feel free to make those changes. Wikipedia is a wiki, so anyone can edit almost any article by simply following the edit this page link at the top.
The Wikipedia community encourages you to be bold in updating pages. Don't worry too much about making honest mistakes—they're likely to be found and corrected quickly. If you're not sure how editing works, check out how to edit a page, or use the sandbox to try out your editing skills. New contributors are always welcome. You don't even need to log in (although there are many reasons why you might want to). --DavidCary (talk) 03:34, 5 June 2015 (UTC)

Really truly awful writing

I have to agree with the previous poster, this article is fairly typical of maths, engineering and technology/medicine articles in Wikipedia. Written by the "experts" for the "experts", with expert not meaning having communication skills in anyway. Binary trees are one of the simplest structures in the universe. How can this article be SO full of waffle that I am scratching my head with each line wondering what I must have missed. It neesds a serious clean up. Start simple, get more complex as you go on if necessary. The first paragraph shoudl not be maths shorthand. How does that help anybody? Communicate people! That is what an encyclopedia is for. Much appreciation to anybody who can clean this article up. It really needs it.

Thank you for your suggestion. When you believe an article needs improvement, please feel free to make those changes. Wikipedia is a wiki, so anyone can edit almost any article by simply following the edit this page link at the top.
The Wikipedia community encourages you to be bold in updating pages. Don't worry too much about making honest mistakes—they're likely to be found and corrected quickly. If you're not sure how editing works, check out how to edit a page, or use the sandbox to try out your editing skills. New contributors are always welcome. You don't even need to log in (although there are many reasons why you might want to). --DavidCary (talk) 03:34, 5 June 2015 (UTC)

Physicists?

In Binary_tree#Types_of_binary_trees "Physicists define a binary tree to mean a full binary tree." The source isn't web so I can't check. Is this a typo? I'm not a physicist but I can't imagine what physicists would use the concept of a binary tree for, and physics/physicists aren't mentioned anywhere else in the article. --Padenton (talk) 16:55, 10 March 2015 (UTC)

removed subtlety from lead

I removed the following sentences from the lead because they addressed a subtlety that is already addressed in the section on defining a binary tree "Using graph theory concepts". The original is preserved here in case someone wants to revert this deletion. If you do the revert, can you also please clean up the English in the mentions of k-ary trees?

There is however a subtle difference between the binary tree data structure as defined here and the notions from graph theory or as K-ary tree is usually defined. As defined here, a binary tree node having a left child but no right child is not the same as a node having a right child but no left child, whereas an ordered/plane tree (or arborescence) from graph theory cannot tell these cases apart, and neither does k-ary as usually understood as using a list of children. An actual generalization of binary tree would have to discern, for example, a case like having a first and third, but no second child; the trie data structure is actually the more appropriate generalization in this respect.

--DavidHolmes0 (talk) 16:23, 2 July 2015 (UTC)

References

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Binary tree. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20101221085950/http://xw2k.nist.gov:80/dads/ to http://xw2k.nist.gov/dads/

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 19:38, 2 November 2016 (UTC)

An empty full tree?

Both in mathematics and in programming there are situations when empty structures or collections are considered: empty set (both in math. set theory and in programming), empty list (a sequence with no terms), empty string, empty file etc. There is sometimes also a reason to consider empty trees.
However, the recursive definition of a full tree in Binary tree#Types of binary trees starts from a single node as a base case, which does not allow for an empty tree, whilst the primary definition does (“a tree in which every node has either 0 or 2 children” is vacuously true for an empty set of nodes). Should we add an explicit case of an empty tree there? --CiaPan (talk) 12:45, 7 March 2019 (UTC)

No: under most definitions/conventions, there is no such thing as an empty tree, ergo in "a tree in which ..." it is the word "tree" that rules out the empty tree. (There may or may not be a graph with no vertices, but if it is a graph, it is not a tree: it does not have the right number of connected components, it does not have the right number of edges, etc.) --JBL (talk) 14:56, 7 March 2019 (UTC)

Thank you. That's right, I have found also in the definitions (Tree (graph theory) § Definitions § Tree):

As elsewhere in graph theory, the order-zero graph (graph with no vertices) is generally not considered to be a tree (...)

CiaPan (talk) 17:52, 7 March 2019 (UTC)

Are binary trees and R-trees reversible (save the NON-operator) or non-reversible

This would be a salient question I reckon. Maybe should have its own section. — Preceding unsigned comment added by 85.76.151.104 (talk) 13:20, 3 May 2022 (UTC)

Balanced / self-balancing binary tree (not BST)

Is there a name for algorithms and trees that maintain balancing property, but are not search trees (i.e. order of nodes do not matter), but tree is used for some aggregation of subtrees instead. (i.e. max value). These have interesting applications, but because they do not need to be ordered, might have way easier balancing strategies than BST. 81.6.34.169 (talk) 23:00, 14 April 2024 (UTC)