Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Binary Tree (Stuff Formally Trained Programmers Know)

DZone's Guide to

Binary Tree (Stuff Formally Trained Programmers Know)

In this post, we take a look at binary trees, how they can be of use for big data professionals for data classification and data implementation.

· Big Data Zone ·
Free Resource

Hortonworks Sandbox for HDP and HDF is your chance to get started on learning, developing, testing and trying out new features. Each download comes preconfigured with interactive tutorials, sample data and developments from the Apache community.

This post is one in a series about stuff formally trained programmers know – the rest of the series can be found here.

Binary Tree

In the previous post, we looked at the tree pattern, which is a theoretical way of structuring data with many advantages. A tree is just a theory though, so what does an actual implementation of it look like? A common data structure implementation is a binary tree.

The name binary tree gives us a hint to how it is structured, each node can have at most 2 child nodes.

Example of annotated binary tree

Classifications

As a binary tree has some flexibility in it, a number of classifications have come up to have a consistent way to discuss a binary tree. Common classifications are: 

  • Full binary tree: Each node in a binary tree can have zero, one, or two child nodes. In a full binary tree, each node can only have zero or two child nodes.

  • Perfect binary tree: This is a full binary tree with the additional condition that all leaf nodes (i.e. nodes with no children) are at the same level/depth.

  • Complete binary tree: The complete binary tree is where each leaf node is as far left as possible.

  • Balanced binary tree: A balanced binary tree is a tree where the height of the tree is as small a number as possible.

Implementations

While a binary tree is more than just a pattern, there are no out of the box implementations in C#, Java, or JavaScript for it. The reason is that it is a very simple data structure and so if you need just the data structure you could implement it yourself but, more importantly, you likely want more than the simple structure - you want a structure that optimizes for traversal or data management.

References

Wikipedia: Binary Tree

Hortonworks Community Connection (HCC) is an online collaboration destination for developers, DevOps, customers and partners to get answers to questions, collaborate on technical articles and share code examples from GitHub.  Join the discussion.

Topics:
big data ,binary tree ,data tree

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}