How to Determine If a Binary Tree Is Symmetric?
A binary tree is one of the ways data is organized in a computer. It is a collection of "records" arranged in a specific way that makes the records easy to access. The binary tree has one entry point --- the root, which is the address of a record. A record can contain any information, but if it is a binary tree, it will always contain two addresses to other records in memory. Ideally, the two addresses in the root will be the beginnings of paths to the same number of records. In other words, the tree will be symmetric.
Other People Are Reading
Instructions
-
-
1
Define some basic terms so we can describe what it means for a tree to be symmetric. The terminal nodes in a tree are called the leaves. In leaf records, both addresses are blank. The addresses in internal nodes have addresses of other records and we say that these addresses "point to the left and right subtrees." A path is what we get if we follow the address links from a node to a leaf. The longest path --- greatest number of records --- from a node is the depth of the tree that starts with that node.
-
2
Write the function that looks at each node in a tree and finds the depth of the subtrees. The standard way to define symmetry in a binary tree is "a binary tree is symmetric if the depths of the subtrees of any node differ by no more than one." The depth function can be described using three cases: The depth from record X is zero if the addresses of both subtrees are blank. If only one address is blank, the depth is one plus the depth of the other subtree. If neither address is blank, the depth is one plus the maximum depths of the two subtrees.
-
-
3
Use the depth function to write the function that tells if a tree is symmetric. Start at the root of the tree and find the depth of each subtree. Call the depths d1 and d2. If d1 = d2, or d1 = d2 + 1 or d2 = d1 + 1, then set the variable s to "true"; otherwise make s "false." return the value of s as the value of the symmetry-test function. At each stage of the symmetry check look at the return from the symmetry-test of the left and right subtrees. If both are symmetric, return the value "true." The final value that is returned from the node will describe the symmetry of the tree.
-
1
Tips & Warnings
Once you find that a node --- including the root --- is unbalanced, you do not need to search the rest of the tree. Building this shortcut into your algorithm can make it a lot faster.
Do not forget to check for the special case when the tree has no nodes. An empty tree shold be considered symmetric.
References
Resources
- Photo Credit Jupiterimages/BananaStock/Getty Images
