Log in
MODULE 11

Binary Tree Calculator: Traversals & Tree Checker

Is This Graph a Tree?

A tree = connected + exactly |V|-1 edges.

Binary Tree Traversal

Level-order list, leave a value blank for "no child": 1,2,3,,5

What is Binary Tree?

A tree is a connected graph with no cycles and exactly one fewer edge than vertices. Trees model hierarchy: file systems, org charts, and search structures. This calculator checks tree validity and walks through traversals.

How Does This Calculator Work?

Enter a binary tree using level-order notation (e.g. 1,2,3,,5 where blanks are empty children), then the calculator checks whether it's a valid tree and walks through preorder, inorder, and postorder traversals one node at a time.

Common Formulas & Rules

  • Root: the top node of a tree, with no parent.
  • Leaf: a node with no children.
  • Binary tree: every node has at most two children.
  • Preorder traversal: visit node, then left subtree, then right subtree.
  • Inorder traversal: visit left subtree, then node, then right subtree.
  • Postorder traversal: visit left subtree, then right subtree, then node.

Worked Example

For the tree with root 1, left child 2, and right child 3 (2 also has a right child 5): preorder visits 1 → 2 → 5 → 3 (node first, then dive left before right), while inorder visits 2 → 5 → 1 → 3 (left subtree fully processed before the node itself is recorded).

Study guide: Trees

Written for students learning this topic for the first time. Last updated October 2026.

Overview

A tree is a connected graph with no cycles. Trees describe file systems, HTML documents, organisation charts, parse trees and decision processes, and special trees such as binary search trees make searching fast.

Several different-looking conditions turn out to be equivalent ways of saying “this is a tree”, and rooted binary trees add traversal orders that show up constantly in programming.

Key ideas explained

Equivalent definitions

For a graph with n vertices, these are equivalent: connected and acyclic; connected with n − 1 edges; acyclic with n − 1 edges; exactly one simple path between any two vertices. Every tree with at least two vertices has at least two leaves.

Rooted and binary trees

A rooted tree has a root, parents, children, leaves and internal vertices. In a binary tree every node has at most two children. A full binary tree with i internal nodes has i + 1 leaves, and a binary tree of height h has at most 2^(h+1) − 1 nodes.

Traversals

Preorder visits root, left, right. Inorder visits left, root, right. Postorder visits left, right, root. Level-order visits row by row (BFS). Inorder on a binary search tree returns the keys in sorted order.

Spanning trees and search trees

A spanning tree of a connected graph keeps all vertices using n − 1 edges; Kruskal's and Prim's algorithms find one of minimum total weight. In a binary search tree, left keys are smaller and right keys larger, so searching takes time proportional to the height, between log n and n.

Worked examples

All four traversals of one tree

Problem. A is the root with children B and C. B has children D and E. C has only a right child F.

  1. Preorder (root first): A, B, D, E, C, F.
  2. Inorder: left subtree of A gives D, B, E; then A; then C's subtree gives C, F.
  3. Postorder (root last): D, E, B, F, C, A.
  4. Level-order: A | B, C | D, E, F.

Answer. Preorder ABDECF, inorder DBEACF, postorder DEBFCA, level-order ABCDEF.

Is it a tree?

Problem. Five vertices with edges AB, BC, CD, DE. Then add AE.

  1. Four edges on five vertices, and the graph is connected: it is a tree (a path).
  2. Adding AE gives five edges and creates the cycle A–B–C–D–E–A.

Answer. The first graph is a tree; the second is not, since it has a cycle.

Enter these same values in the calculator above and compare each step with the working shown here.

Common mistakes to avoid

  • Thinking n − 1 edges alone proves a tree. The graph must also be connected (or acyclic).
  • Mixing up traversal orders. In preorder the root is first; in postorder it is last.
  • Assuming a binary search tree is balanced. Inserting sorted keys produces a chain of height n − 1.
  • Mixing up height, depth and number of levels, which differ by conventions. State yours.

Where this shows up in computer science

  • File systems and database indexes (B-trees) are trees.
  • Compilers build abstract syntax trees, and postorder traversal evaluates expression trees.
  • Decision trees, game trees and Huffman coding trees are used in machine learning, AI and compression.

Test yourself

Try each question before opening the answer.

How many edges does a tree with 12 vertices have?

11.

A full binary tree has 10 internal nodes. How many leaves and nodes in total?

11 leaves and 21 nodes.

Which traversal of a binary search tree visits keys in sorted order?

Inorder.

Frequently asked questions

How do I know if a graph is a tree?

A graph is a tree if and only if it's connected and has exactly one fewer edge than vertices (|E| = |V| - 1). Both conditions must hold; either alone isn't sufficient.

What's the difference between preorder and postorder traversal?

Preorder visits the node itself first, then its left and right subtrees. Postorder visits both subtrees first and records the node last. Inorder sits in between, visiting left subtree, then node, then right subtree.

What is a leaf node?

A leaf is a node with no children — it sits at the "end" of a branch in the tree, with nothing beneath it.