A binary tree is either **empty** or consists of a node called the **root** together with two binary trees called the **left subtree** and the **right subtree**.

**Some Facts:**

- If
*h*= height of a binary tree, - max # of leaves = 2
^{h} - max # of nodes = 2
^{h + 1}– 1 - Total number of binary trees having
*n*nodes- = number of stack-realizable permutations of length
*n* - = number of well-formed parentheses (with n left parentheses and n right parentheses)
- =(1/n+1)(2n
**C**n) [Catalan Number]A binary tree with height*h*and 2^{h + 1}– 1 nodes (or 2^{h}leaves) is called a**full binary tree**

- = number of stack-realizable permutations of length
- A binary tree with
*n*nodes is said to be**complete**if it contains all the first*n*nodes of the following numbering scheme1

/ \

2 3

/ \ /

4 5 6 - .Following is not complete binary tree
4

/ \

2 7

/ \ \

1 3 9 - In a (balanced) binary tree with
`m`

nodes, moving from one level to the next requires one comparison, and there are`log_2(m)`

levels, for a total of`log_2(m)`

comparisons. - In contrast, an n-ary tree will require
`log_2(n)`

comparisons*(using a binary search)*to move to the next level. Since there are`log_n(m)`

total levels, the search will require`log_2(n)*log_n(m)`

=`log_2(m)`

comparisons total. So, though n-ary trees are more complex, they provide no advantage in terms of total comparisons necessary. - The reason that binary trees are used more often than n-ary trees for searching is that n-ary trees are more complex, but usually provide no real speed advantage.

**Binary Tree Traversal:**

- 1.
**Preorder**

Visit root, visit left subtree in preorder, visit right subtree in preorder

- 2.
**Postorder**

Visit left subtree in postorder, right subtree in postorder, then the root

- 3.
**Inorder**

Example 1:

Example 2 :

**Programming perspective**

A binary tree is a structure comprising nodes, where each node has the following 3 components:

**Data element:**Stores any kind of data in the node**Left pointer:**Points to the tree on the left side of node**Right pointer:**Points to the tree on the right side of the node

As the name suggests, the **data** element stores any kind of data in the node.

The **left** and **right** pointers point to binary trees on the left and right side of the node respectively.

If a tree is empty, it is represented by a **null** pointer.

**Commonly-used terminologies**

**Root**: Top node in a tree**Child**: Nodes that are next to each other and connected downwards**Parent**: Converse notion of child**Siblings**: Nodes with the same parent**Descendant**: Node reachable by repeated proceeding from parent to child**Ancestor**: Node reachable by repeated proceeding from child to parent.**Leaf**: Node with no children**Internal node**: Node with at least one child**External node**: Node with no children

**Binary Tree Java Implementation :**

/* * Binary Tree Java Implementation * Includes tree traversal. (Preorder, Postorder, Inorder) */ import java.util.Scanner; /* Class BTNode */ class BTNode { BTNode left, right; int data; /* Constructor */ public BTNode() { left = null; right = null; data = 0; } /* Constructor */ public BTNode(int n) { left = null; right = null; data = n; } /* Function to set left node */ public void setLeft(BTNode n) { left = n; } /* Function to set right node */ public void setRight(BTNode n) { right = n; } /* Function to get left node */ public BTNode getLeft() { return left; } /* Function to get right node */ public BTNode getRight() { return right; } /* Function to set data to node */ public void setData(int d) { data = d; } /* Function to get data from node */ public int getData() { return data; } } /* Class BT */ class BT { private BTNode root; /* Constructor */ public BT() { root = null; } /* Function to check if tree is empty */ public boolean isEmpty() { return root == null; } /* Functions to insert data */ public void insert(int data) { root = insert(root, data); } /* Function to insert data recursively */ private BTNode insert(BTNode node, int data) { if (node == null) node = new BTNode(data); else { if (node.getRight() == null) node.right = insert(node.right, data); else node.left = insert(node.left, data); } return node; } /* Function to count number of nodes */ public int countNodes() { return countNodes(root); } /* Function to count number of nodes recursively */ private int countNodes(BTNode r) { if (r == null) return 0; else { int l = 1; l += countNodes(r.getLeft()); l += countNodes(r.getRight()); return l; } } /* Function to search for an element */ public boolean search(int val) { return search(root, val); } /* Function to search for an element recursively */ private boolean search(BTNode r, int val) { if (r.getData() == val) return true; if (r.getLeft() != null) if (search(r.getLeft(), val)) return true; if (r.getRight() != null) if (search(r.getRight(), val)) return true; return false; } /* Function for inorder traversal */ public void inorder() { inorder(root); } private void inorder(BTNode r) { if (r != null) { inorder(r.getLeft()); System.out.print(r.getData() +" "); inorder(r.getRight()); } } /* Function for preorder traversal */ public void preorder() { preorder(root); } private void preorder(BTNode r) { if (r != null) { System.out.print(r.getData() +" "); preorder(r.getLeft()); preorder(r.getRight()); } } /* Function for postorder traversal */ public void postorder() { postorder(root); } private void postorder(BTNode r) { if (r != null) { postorder(r.getLeft()); postorder(r.getRight()); System.out.print(r.getData() +" "); } } } /* Class BinaryTree */ public class BinaryTree { public static void main(String[] args) { Scanner scan = new Scanner(System.in); /* Creating object of BT */ BT bt = new BT(); /* Perform tree operations */ System.out.println("Binary Tree Test\n"); char ch; do { System.out.println("\nBinary Tree Operations\n"); System.out.println("1. insert "); System.out.println("2. search"); System.out.println("3. count nodes"); System.out.println("4. check empty"); int choice = scan.nextInt(); switch (choice) { case 1 : System.out.println("Enter integer element to insert"); bt.insert( scan.nextInt() ); break; case 2 : System.out.println("Enter integer element to search"); System.out.println("Search result : "+ bt.search( scan.nextInt() )); break; case 3 : System.out.println("Nodes = "+ bt.countNodes()); break; case 4 : System.out.println("Empty status = "+ bt.isEmpty()); break; default : System.out.println("Wrong Entry \n "); break; } /* Display tree */ System.out.print("\nPost order : "); bt.postorder(); System.out.print("\nPre order : "); bt.preorder(); System.out.print("\nIn order : "); bt.inorder(); System.out.println("\n\nDo you want to continue (Type y or n) \n"); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } }

### Applications of binary trees

- Binary Search Tree – Used in
*many*search applications where data is constantly entering/leaving, such as the`map`

and`set`

objects in many languages’ libraries. These are a data structure in which searching, insertion, and removal are all very fast (about`log(n)`

operations). - Binary Space Partition – Used in almost every 3D video game to determine what objects need to be rendered.
- Binary Tries – Used in almost every high-bandwidth router for storing router-tables.
- Hash Trees – used in p2p programs and specialized image-signatures in which a hash needs to be verified, but the whole file is not available.
- Heaps – Used in implementing efficient priority-queues, which in turn are used for scheduling processes in many operating systems, Quality-of-Service in routers, and A*
*(path-finding algorithm used in AI applications, including robotics and video games)*. Also used in heap-sort. - Huffman Coding Tree – used in compression algorithms, such as those used by the .jpeg and .mp3 file-formats.
- GGM Trees – Used in cryptographic applications to generate a tree of pseudo-random numbers.
- Syntax Tree – Constructed by compilers and (implicitly) calculators to parse expressions.
- Treap – Randomized data structure used in wireless networking and memory allocation.
- T-tree – Though most databases use some form of B-tree to store data on the drive, databases which keep all (most) their data in memory often use T-trees to do so.
- a Manipulate hierarchical data
- Make information easy to search (see tree traversal)
- Manipulate sorted lists of data
- Use as a workflow for compositing digital images for visual effects
- Use in router algorithms

Comment or email us [email protected] if you have any questions related to binary tree.