A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.

### Implementation

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace BTree { public class Node { public int Data { get; set; } public Node Left { get; set; } public Node Right { get; set; } public Node() { } public Node(int data) { this.Data = data; } } public class BinaryTree { private Node _root; public BinaryTree() { _root = null; } public void Insert(int data) { // 1. If the tree is empty, return a new, single node if (_root == null) { _root = new Node(data); return; } // 2. Otherwise, recur down the tree InsertRec(_root, new Node(data)); } private void InsertRec(Node root, Node newNode) { if (root == null) root = newNode; if (newNode.Data < root.Data) { if (root.Left == null) root.Left = newNode; else InsertRec(root.Left, newNode); } else { if (root.Right == null) root.Right = newNode; else InsertRec(root.Right, newNode); } } private void DisplayTree(Node root) { if (root == null) return; DisplayTree(root.Left); System.Console.Write(root.Data + " "); DisplayTree(root.Right); } public void DisplayTree() { DisplayTree(_root); } } class Program { static void Main(string[] args) { BinaryTree tree = new BinaryTree(); Node root = new Node(); tree.Insert(4); tree.Insert(2); tree.Insert(5); tree.Insert(1); tree.Insert(3); tree.DisplayTree(); } } }

## Comments

## Post a Comment