---
description: Tree is a non-linear data structure.
---

# What's Binary Tree & Implementation?

_**Binary trees**_ and _**n-ary trees**_ are two different types of data structures commonly used in computer science, each with its own advantages and use cases.

<table><thead><tr><th>Binary Tree  -  (child &#x3C;= 2)</th><th>N-ary Tree  -   (n - childs)</th></tr></thead><tbody><tr><td>A <mark style="color:blue;">binary tree</mark> is a tree data structure in which each node has at most <mark style="color:blue;"><strong>two children</strong></mark>, referred to as the <code>left</code> child and the <code>right</code> child.</td><td>An <mark style="color:blue;">n-ary tree</mark> is a tree data structure in which each node can have <mark style="color:blue;"><strong>up to n children</strong></mark>.</td></tr><tr><td><pre class="language-cpp"><code class="lang-cpp">Node {
    int data;
    Node* left;
    Node* right;
}
</code></pre></td><td><pre class="language-cpp"><code class="lang-cpp">Node {
    int data;
    List&#x3C;Node*> child;
}
</code></pre></td></tr><tr><td>Binary trees are often used in binary search trees (BSTs) where data is organized in a <mark style="color:red;">sorted</mark> manner, allowing for efficient <code>search</code>, <code>insertion</code>, and <code>deletion</code> operations.</td><td>N-ary trees are more flexible and versatile than binary trees because they can represent data structures where nodes have varying numbers of children.</td></tr><tr><td>Common operations on binary trees include <mark style="color:blue;">tree traversal algorithms</mark> like <code>inorder</code>, <code>preorder</code>, and <code>postorder</code> traversal.</td><td>Common examples of n-ary trees include <mark style="color:blue;">file systems</mark>, <mark style="color:blue;">organization hierarchies</mark>, and <mark style="color:blue;">parse trees</mark> in linguistics.</td></tr><tr><td>Binary trees are simple to implement and understand, and they are efficient for certain types of operations, particularly those that involve <mark style="color:red;">comparison-based searching.</mark></td><td>N-ary trees are efficient for representing hierarchical data where the <mark style="color:red;">number of children per node can vary widely</mark>.</td></tr><tr><td>However, they might not be the most efficient choice for scenarios where nodes typically have <mark style="color:red;">more than two children</mark>, as they can lead to unbalanced trees in such cases, impacting performance.</td><td>However, they can be more complex to implement and reason about compared to binary trees, especially for certain operations like <mark style="color:red;">traversal</mark>.</td></tr></tbody></table>

* The choice between binary trees and n-ary trees often depends on the specific requirements of the problem being solved. If the data naturally fits into a hierarchy with a fixed number of children per node, an n-ary tree might be more appropriate. Otherwise, if the data is naturally organized in a binary manner, a binary tree might be a better choice.

### Binary Tree

A binary tree is a hierarchical data structure that simulates a tree structure with a single root node, internal nodes, and leaf nodes.

* <mark style="color:red;">**Node:**</mark> Any Element of any Tree called Node.
* <mark style="color:red;">**Root Node:**</mark> The uppermost and central node in the tree. [Binary Tree](https://en.wikipedia.org/wiki/Binary_tree)
* <mark style="color:red;">**Parent Nodes:**</mark> Also known as **Internal** nodes, these contain data and references to child nodes.
* <mark style="color:red;">**Child Nodes:**</mark> Nodes connected to a parent node. A node can have zero, one, or two child nodes.
* <mark style="color:red;">**Siblings:**</mark> Nodes that share the same parent are siblings, like leaves growing from the same branch.
* <mark style="color:red;">**Ancestor:**</mark> Any node higher up in the tree from another node is its ancestor. The <mark style="color:red;">**root**</mark> is the ultimate ancestor of all nodes.
* <mark style="color:red;">**Descendant:**</mark> Any node lower down in the tree from another node is its descendant. Children are the direct descendants of their parents.
* <mark style="color:red;">**Leaf Nodes:**</mark> Also known as terminal nodes, these are the nodes at the bottom of the tree with no child nodes.

<div data-full-width="true"><figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2FbiU2jGO37HI0wzCQWK3o%2Fq1mo5udvxvisjxofj2r1.png?alt=media&#x26;token=3d3fd82e-0daa-4987-baf8-cee28b2e381b" alt="" width="375"><figcaption><p>n-ary Tree</p></figcaption></figure></div>
