> For the complete documentation index, see [llms.txt](https://dsa-cpp.gitbook.io/nafees/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dsa-cpp.gitbook.io/nafees/binary-tree/whats-binary-tree-and-implementation.md). # What's Binary Tree & Implementation? Tree is a non-linear data structure. ***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.
Binary Tree - (child <= 2)N-ary Tree - (n - childs)
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.An n-ary tree is a tree data structure in which each node can have up to n children.
Node {
    int data;
    Node* left;
    Node* right;
}

Node {
    int data;
    List<Node*> child;
}
Binary trees are often used in binary search trees (BSTs) where data is organized in a sorted manner, allowing for efficient search, insertion, and deletion operations.N-ary trees are more flexible and versatile than binary trees because they can represent data structures where nodes have varying numbers of children.
Common operations on binary trees include tree traversal algorithms like inorder, preorder, and postorder traversal.Common examples of n-ary trees include file systems, organization hierarchies, and parse trees in linguistics.
Binary trees are simple to implement and understand, and they are efficient for certain types of operations, particularly those that involve comparison-based searching.N-ary trees are efficient for representing hierarchical data where the number of children per node can vary widely.
However, they might not be the most efficient choice for scenarios where nodes typically have more than two children, as they can lead to unbalanced trees in such cases, impacting performance.However, they can be more complex to implement and reason about compared to binary trees, especially for certain operations like traversal.
* 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. * **Node:** Any Element of any Tree called Node. * **Root Node:** The uppermost and central node in the tree. [Binary Tree](https://en.wikipedia.org/wiki/Binary_tree) * **Parent Nodes:** Also known as **Internal** nodes, these contain data and references to child nodes. * **Child Nodes:** Nodes connected to a parent node. A node can have zero, one, or two child nodes. * **Siblings:** Nodes that share the same parent are siblings, like leaves growing from the same branch. * **Ancestor:** Any node higher up in the tree from another node is its ancestor. The **root** is the ultimate ancestor of all nodes. * **Descendant:** Any node lower down in the tree from another node is its descendant. Children are the direct descendants of their parents. * **Leaf Nodes:** Also known as terminal nodes, these are the nodes at the bottom of the tree with no child nodes.

n-ary Tree