Editing Binary tree (section)

== Properties of binary trees ==
* The number of nodes {{mvar|n}} in a '''full''' binary tree is at least <math>2h+1</math> and at most <math>2^{h+1}-1 </math> (i.e., the number of nodes in a '''perfect''' binary tree), where {{mvar|h}} is the [[Glossary of graph theory terms#H|height]] of the tree. A tree consisting of only a root node has a height of 0. The least number of nodes is obtained by adding only two children nodes per adding height so <math>2h+1</math> (1 for counting the root node). The maximum number of nodes is obtained by fully filling nodes at each level, i.e., it is a perfect tree. For a perfect tree, the number of nodes is <math>1 + 2 + 4 + \ldots + 2^h = 2^{h + 1} - 1</math>, where the last equality is from the [[geometric series]] sum.
* The number of leaf nodes {{mvar|l}} in a '''perfect''' binary tree is <math>l = (n + 1) / 2</math> (where {{mvar|n}} is the number of nodes in the tree) because <math>n={{2}^{h+1}}-1</math> (by using the above property) and the number of leaves is <math>2^h</math> so <math>n=2\cdot {{2}^{h}}-1=2l-1\to l=\left( n+1 \right)/2</math>. It also means that <math>n = 2l - 1</math>. In terms of the tree height {{mvar|h}}, <math>l = (2^{h+1}-1 + 1) / 2 = 2^h</math>.
* For any non-empty binary tree with <math>l  </math> leaf nodes and <math>i_2  </math> nodes of degree 2 (internal nodes with two child nodes), <math>l = i_2 + 1  </math>.<ref>{{cite book |last=Mehta |first=Dinesh |title=Handbook of Data Structures and Applications |author2=Sartaj Sahni |publisher=[[Chapman and Hall]] |year=2004 |isbn=1-58488-435-5 |author-link2=Sartaj Sahni}}</ref> The proof is the following. For a perfect binary tree, the total number of nodes is <math>n = 2^{h+1}-1 </math> (A perfect binary tree is a full binary tree.) and <math>l = 2^h</math>, so <math>i = n - l = (2^{h+1}-1) - 2^h = 2^h - 1 = l - 1 \to l = i + 1  </math>. To make a full binary tree from a perfect binary tree, a pair of two sibling nodes are removed one by one. This results in "two leaf nodes removed" and "one internal node removed" and "the removed internal node becoming a leaf node", so one leaf node and one internal node is removed per removing two sibling nodes. As a result, <math>l = i + 1</math> also holds for a full binary tree. To make a binary tree with a leaf node without its sibling, a single leaf node is removed from a full binary tree, then "one leaf node removed" and "one internal nodes with two children removed" so <math>l = i + 1</math> also holds. This relation now covers all non-empty binary trees.
* With given {{mvar|n}} nodes, the minimum possible tree height is <math>h_{\min} = \log_2 (n+1)-1  </math> with which the tree is a balanced full tree or perfect tree. With a given height {{mvar|h}}, the number of nodes can't exceed the <math>2^{h+1}-1 </math> as the number of nodes in a perfect tree. Thus <math>n \leq 2^{h + 1} - 1 \to h \geq \log _2 (n + 1) - 1</math>.
* A binary Tree with {{mvar|l}} leaves has at least the height <math>h_m = \log_2 (l)</math>. With a given height {{mvar|h}}, the number of leaves at that height can't exceed <math>2^h</math> as the number of leaves at the height in a perfect tree. Thus <math>l \leq 2^h \to h \geq \log_2 (l)</math>.
* In a non-empty binary tree, if {{mvar|n}} is the total number of nodes and {{mvar|e}} is the total number of edges, then <math>e = n - 1</math>. This is obvious because each node requires one edge except for the root node.
* The number of null links (i.e., absent children of the nodes) in a binary tree of {{mvar|n}} nodes is {{math|(''n'' + 1)}}.
* The number of internal nodes in a '''complete''' binary tree of {{mvar|n}} nodes is <math>\lfloor n/2\rfloor </math>.