Find the inorder, preorder, postorder and level-order traversals of a binary tree from its level-order list, or rebuild one traversal from an inorder pair.

Comma-separated; null or none marks an absent node. At most 512 nodes and 1,023 positions.

Sample tree

Related Calculators

Perfect Binary Tree Node Count Formula

The following formula gives the total number of nodes N in a perfect binary tree (all levels completely filled). If a traversal visits every node exactly once, then the number of nodes visited is also N.

N = 2h - 1

Variables:

  • N is the total number of nodes in the tree (and the number of nodes visited by a full traversal)
  • h is the height measured as the number of levels in the tree (root is level 1). (If you define height as the number of edges on the longest root-to-leaf path, the equivalent perfect-tree formula is N = 2^(h+1) − 1.)

Note: for a nonempty complete (but not necessarily perfect) binary tree, height alone does not determine the exact node count. With h ≥ 1 levels, the count ranges from 2^(h−1) to 2^h − 1. This calculator defines the empty tree as 0 levels and 0 nodes. Perfect-tree inverse mode accepts only counts 2^h − 1, using exact integer arithmetic up to 2,048 levels.

What is a Tree Traversal?

Tree traversal is a process used in computer science to visit or check each node in a tree data structure. This can be done in different ways, including depth-first order (pre-order, in-order, post-order) and breadth-first order (level order). The traversal method chosen often depends on the specific needs of the algorithm being used. This process is crucial in tasks such as searching for a specific value in the tree, checking the structure of the tree, or applying an operation to each node.

How to Calculate Tree Traversal?

The following steps calculate a perfect-tree node count. For actual traversal sequences, choose a traversal task. Preorder visits root-left-right; inorder left-root-right; postorder left-right-root; level-order visits breadth first. Enter comma-separated, case-sensitive labels. Paired reconstruction requires unique labels and two consistent sequences. At most 512 present nodes and 64 characters per label are supported. In level-order mode, null or none marks an absent node. Choose indexed positions (children 2i+1, 2i+2 using zero-based indices) or compact queue encoding (child slots only for present parents). Indexed nodes with absent parents are rejected rather than silently dropped; at most 1,023 positions are supported. Optional samples fill explicit example inputs and still require Calculate.

  1. Determine the height of the tree as the number of levels (h).
  2. If the tree is perfect, use the formula N = 2^h − 1 to calculate the total number of nodes (and thus nodes visited).
  3. Calculate the result.
  4. Check your answer (for example, by counting nodes level-by-level).

Example Problem:

Use the following variables as an example problem to test your knowledge.

Height of the tree (h) = 3 (levels) → N = 2^3 − 1 = 7 nodes