Binary Trees

In computer science, a binary tree is a hierarchical data structure where each node can have at most two children. The two children are usually referred to as the left child and right child.

Binary trees have various applications, including:

• Representing hierarchical relationships, such as the file system structure.
• Implementing efficient searching and sorting algorithms, such as binary search and binary heap.
• Representing expressions in parsing and evaluating mathematical expressions.

Properties of Binary Trees:

• Root: The topmost node of a binary tree is called the root node.
• Parent node: Any node in the tree, except the root node, has a unique parent node.
• Child node: Each parent node can have at most two child nodes, which are connected through edges.
• Leaf node: A node without any children is called a leaf node.
• Binary search property: For a binary search tree, all the nodes in the left subtree have a value less than the root node, and all the nodes in the right subtree have a value greater than the root node.

Let's take a look at an example of creating a binary tree in C++:

1#include <iostream>
2using namespace std;
3
4struct Node {
5    int data;
6    Node* left;
7    Node* right;
8};
9
10/* This function is only for creating a new node */
11Node* newNode(int data)
12{
13    Node* node = new Node;
14    node->data = data;
15    node->left = nullptr;
16    node->right = nullptr;
17
18    return (node);
19}
20
21int main() {
22    // Create a root node
23    Node* root = newNode(1);
24
25    // Create left and right children of root
26    root->left = newNode(2);
27    root->right = newNode(3);
28
29    // Create left and right children of the left child
30    root->left->left = newNode(4);
31    root->left->right = newNode(5);
32
33    return 0;
34}

In this example, we create a binary tree with a root node having a value of 1. The left child of the root node has a value of 2, and the right child has a value of 3. Additionally, the left child of the left child has a value of 4, and the right child of the left child has a value of 5.

Binary trees are fundamental data structures with various applications and properties. Understanding binary trees is crucial for designing efficient algorithms and solving problems in computer science.

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

struct Node {

    int data;

    Node* left;

    Node* right;

};

​

/* This function is only for creating a new node */

Node* newNode(int data)

{

    Node* node = new Node;

    node->data = data;

    node->left = nullptr;

    node->right = nullptr;

​

    return (node);

}

​

int main() {

    // Create a root node

    Node* root = newNode(1);

​

    // Create left and right children of root

    root->left = newNode(2);

    root->right = newNode(3);

​

    // Create left and right children of the left child