"BinaryTree" (Data Structure)
"BinaryTree"
represents a mutable binary tree where the values stored at each node are general expressions.
Details



- A binary tree is useful for accessing nodes based on data associated with each node as well as for representing hierarchical relationships with up to two branches:
-
CreateDataStructure["BinaryTree",v] create a new "BinaryTree" with specified initial value v and empty left and right children CreateDataStructure["BinaryTree",v{l,r}] create a new "BinaryTree" with specified initial value v and specified left and right children Typed[x,"BinaryTree"] give x the type "BinaryTree" - For a data structure of type "BinaryTree", the following operations can be used:
-
ds["BreadthFirstScan",f] perform a breadth-first scan of ds, passing the data in each node to f time: O(n) ds["Copy"] return a copy of ds time: O(n) ds["Data"] return the data stored in the tree node ds time: O(1) ds["InOrderScan",f] perform an in-order scan of ds, passing the data in each node to f time: O(n) ds["Left"] return the data structure for the left child of ds time: O(1) ds["LeftNullQ"] return True if the left child of ds is null time: O(1) ds["NullQ"] return True if ds is null time: O(1) ds["PostOrderScan",f] perform a post-order scan of ds, passing the data in each node to f time: O(n) ds["PreOrderScan",f] perform a pre-order scan of ds, passing the data in each node to f time: O(n) ds["Right"] return the data structure for the right child of ds time: O(1) ds["RightNullQ"] return True if the right child of ds is null time: O(1) ds["SetData",v] set the data stored in the tree node ds to v time: O(1) ds["SetLeft",l] set the left child of the tree node ds to l time: O(1) ds["SetRight",r] set the right child of the tree node ds to r time: O(1) ds["ValidQ"] return True if ds is a valid tree time: O(n) ds["Visualization"] return a visualization of ds time: O(n) - The following functions are also supported:
-
dsi===dsj True, if dsi equals dsj FullForm[ds] the full form of ds Information[ds] information about ds InputForm[ds] the input form of ds Normal[ds] convert ds to a normal expression
Examples
open allclose allBasic Examples (2)Summary of the most common use cases
A new "BinaryTree" can be created with CreateDataStructure:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-n9py1n


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-84r1md

Insert a new value to be stored:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-tnm4iz

Confirm that the value has updated:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-t2e3rl


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-fhlt9u


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-hpys0e

Create a new "BinaryTree" with specified children:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-sgews4


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-6nfgcf


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-89keh6

Return an expression version of ds:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-dbekgb

A visualization of the data structure can be generated:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-uvwa1b

Scope (1)Survey of the scope of standard use cases
Information (1)
A new "BinaryTree" can be created with CreateDataStructure:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-fip55w

Information about the data structure ds:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-5du3om

Applications (7)Sample problems that can be solved with this function
Binary Search Tree (1)
One use of a binary tree is for storing ordered material. Typically these are called binary search trees. Here is a simple insertion program:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-112oeq
Create a binary tree and insert 30 random numbers:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-mndpfn

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-1ac6qt

This makes an in-order scan over the binary tree. Since it is sorted, the elements are visited in sorted order, as shown in this example:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-0ydqj6

A problem with a basic binary search tree like this is that the insertion chains can become unbalanced, so that the maximum depth of the tree becomes large. This problem is corrected by the various forms of balanced binary trees.
Tree Rotation (1)
Tree rotation on a sorted binary tree involves a change to the structure of the tree while maintaining the order of elements. Rotations are used by many techniques for creating balanced binary trees.
Some basic tree rotation operations for right and left rotations are shown here:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-mn17gd

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-cuqf6j
A binary tree is created here. Note that it has two levels of nodes on the left and none on the right. This is an inefficient storage:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-4i7y7m

The right rotation moves the nodes to the right, maintaining the sorted property and making a more balanced tree:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-l39c5k

The left rotation moves the nodes back to the left, also maintaining the sorted property:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-2dlkuh

RandomTree (1)
Compute the Maximum Depth of a Binary Tree (1)
The maximum depth of a binary tree is the number of nodes along the longest path from the root node to a leaf node.
A program to compute the maximum depth of a binary tree:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-9e0vuh

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-4oj4ql


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-f8qbk3

Find the Lowest Common Ancestor (1)
The lowest common ancestor of two nodes in a tree is the lowest (or deepest) node that has both nodes as a descendant. It can be computed with some simple code.
A program to insert random nodes into a tree. This uses a counter to make sure that all nodes are distinct:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-eugq1t
Set the random seed to get a reproducible example:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-u53nnu
Create a random tree and visualize it:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-lan7p8

A program to find the lowest common ancestor:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-ftzfr1
Find the lowest common denominator:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-2wz2u4

A visualization is a good way to verify the solution:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-6xbu9m

Test if a Binary Tree is Symmetric (1)
A binary tree is symmetric if it there is a plane of symmetry down its middle.
A program to test if a binary tree is symmetric. It checks that the data is equal and that the left and right nodes are symmetric:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-tax7el

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-uga703


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-0u84li


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-ml2797


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-tg14m8

Find the Diameter of a Binary Tree (1)
The diameter of a binary tree is the length of the longest path between any two nodes (which might or might not pass through the root).
A program to compute the diameter of a binary tree:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-iap2w2

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-56gc3a


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-d0u7u8


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-vi2o2t


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-9srmwf

Possible Issues (2)Common pitfalls and unexpected behavior
Null Nodes (1)
Create a binary tree with some data:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-j180rz


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-billch


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-xb788

It is an error to carry out operations that work on the contents of a null node:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-8tk0be


The serialization of a null node is Null:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-72pok6


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-ra7fe

Create a null node with CreateDataStructure:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-7dlnnr


https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-f47yvg

A Wolfram Language representation of a null node is very useful, since it allows algorithms to be written that manipulate the nodes of a binary tree without having to check if they are null.
Valid Trees (1)
The Wolfram Language interface to binary trees is designed to be flexible and efficient. This has some consequences for the structures created.
Create a binary tree with some data:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-vxfxtr

Create another tree and make it the right child:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-ph3sqr

Now there is nothing in the operations that prevents making the right child equal to the parent:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-je631f
The result is no longer a tree. This can be confirmed by using the "ValidQ" operation:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-0scf9g

Some operations give errors if the tree is not valid:

https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-rn6ylb


The insertion functions do not give errors when an invalid structure is created because this would make them less efficient. Operations such as those that serialize the data structure have a built-in check.