WOLFRAM

Wolfram Language & System Documentation Center
Wolfram Language Home Page »

"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 ftime: O(n)
    ds["Copy"]return a copy of dstime: O(n)
    ds["Data"]return the data stored in the tree node dstime: O(1)
    ds["InOrderScan",f]perform an in-order scan of ds, passing the data in each node to ftime: O(n)
    ds["Left"]return the data structure for the left child of dstime: O(1)
    ds["LeftNullQ"]return True if the left child of ds is nulltime: O(1)
    ds["NullQ"]return True if ds is nulltime: O(1)
    ds["PostOrderScan",f]perform a post-order scan of ds, passing the data in each node to ftime: O(n)
    ds["PreOrderScan",f]perform a pre-order scan of ds, passing the data in each node to ftime: O(n)
    ds["Right"]return the data structure for the right child of dstime: O(1)
    ds["RightNullQ"]return True if the right child of ds is nulltime: O(1)
    ds["SetData",v]set the data stored in the tree node ds to vtime: O(1)
    ds["SetLeft",l]set the left child of the tree node ds to ltime: O(1)
    ds["SetRight",r]set the right child of the tree node ds to rtime: O(1)
    ds["ValidQ"]return True if ds is a valid treetime: O(n)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, 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 all

Basic Examples  (2)Summary of the most common use cases

A new "BinaryTree" can be created with CreateDataStructure:

In[1]:=1
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-n9py1n
Out[1]=1

Extract the value stored:

In[2]:=2
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-84r1md
Out[2]=2

Insert a new value to be stored:

In[3]:=3
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-tnm4iz
Out[3]=3

Confirm that the value has updated:

In[4]:=4
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-t2e3rl
Out[4]=4

The left child is null:

In[5]:=5
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-fhlt9u
Out[5]=5

The right child is null:

In[6]:=6
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-hpys0e
Out[6]=6

Create a new "BinaryTree" with specified children:

In[1]:=1
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-sgews4
Out[1]=1

There is a left child:

In[2]:=2
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-6nfgcf
Out[2]=2

Return the left child:

In[3]:=3
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-89keh6
Out[3]=3

Return an expression version of ds:

In[4]:=4
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-dbekgb
Out[4]=4

A visualization of the data structure can be generated:

In[5]:=5
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-uvwa1b
Out[5]=5

Scope  (1)Survey of the scope of standard use cases

Information  (1)

A new "BinaryTree" can be created with CreateDataStructure:

In[1]:=1
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-fip55w
Out[1]=1

Information about the data structure ds:

In[2]:=2
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-5du3om
Out[2]=2

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:

In[1]:=1
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-112oeq

Create a binary tree and insert 30 random numbers:

In[2]:=2
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-mndpfn
In[3]:=3
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-1ac6qt
Out[3]=3

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:

In[4]:=4
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-0ydqj6
Out[4]=4

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:

In[1]:=1
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-mn17gd
In[2]:=2
✖
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:

In[3]:=3
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-4i7y7m
Out[3]=3

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

In[4]:=4
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-l39c5k
Out[4]=4

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

In[5]:=5
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-2dlkuh
Out[5]=5

RandomTree  (1)

A program to insert random nodes into a binary tree to a specified depth:

In[1]:=1
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-t53aho
In[2]:=2
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-4ep678
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-8dpy3d
Out[3]=3

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:

In[1]:=1
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-9e0vuh

A sample tree:

In[2]:=2
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-4oj4ql
Out[2]=2

The maximum depth:

In[3]:=3
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-f8qbk3
Out[3]=3

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:

In[1]:=1
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-eugq1t

Set the random seed to get a reproducible example:

In[2]:=2
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-u53nnu

Create a random tree and visualize it:

In[3]:=3
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-lan7p8
Out[3]=3

A program to find the lowest common ancestor:

In[4]:=4
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-ftzfr1

Find the lowest common denominator:

In[5]:=5
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-2wz2u4
Out[5]=5

A visualization is a good way to verify the solution:

In[6]:=6
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-6xbu9m
Out[6]=6

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:

In[1]:=1
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-tax7el

A tree that is not symmetric:

In[2]:=2
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-uga703
Out[2]=2

Verified as nonsymmetric:

In[3]:=3
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-0u84li
Out[3]=3

A tree that is symmetric:

In[4]:=4
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-ml2797
Out[4]=4

Verified as symmetric:

In[5]:=5
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-tg14m8
Out[5]=5

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:

In[1]:=1
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-iap2w2

A sample tree:

In[2]:=2
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-56gc3a
Out[2]=2

Compute the diameter:

In[3]:=3
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-d0u7u8
Out[3]=3

Another sample tree:

In[4]:=4
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-vi2o2t
Out[4]=4

Compute the diameter:

In[5]:=5
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-9srmwf
Out[5]=5

Possible Issues  (2)Common pitfalls and unexpected behavior

Null Nodes  (1)

Create a binary tree with some data:

In[1]:=1
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-j180rz
Out[1]=1

Extract the right child:

In[2]:=2
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-billch
Out[2]=2

This is a null node:

In[3]:=3
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-xb788
Out[3]=3

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

In[4]:=4
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-8tk0be
Out[4]=4

The serialization of a null node is Null:

In[5]:=5
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-72pok6
In[6]:=6
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-ra7fe
Out[6]=6

Create a null node with CreateDataStructure:

In[7]:=7
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-7dlnnr
Out[7]=7
In[8]:=8
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-f47yvg
Out[8]=8

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:

In[1]:=1
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-vxfxtr
Out[1]=1

Create another tree and make it the right child:

In[2]:=2
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-ph3sqr
Out[2]=2

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

In[3]:=3
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-je631f

The result is no longer a tree. This can be confirmed by using the "ValidQ" operation:

In[4]:=4
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-0scf9g
Out[4]=4

Some operations give errors if the tree is not valid:

In[5]:=5
✖
https://wolfram.com/xid/0dnn08lzka49y4wyn0tsu60-rn6ylb
Out[5]=5

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.