Stack Overflow
Stack Overflow

Questions tagged [binary-tree]

A tree data structure in which each node has at most two child nodes.

Binary trees are data structures in which each node has at most two child nodes, called the left child and the right child of the node.

Nodes with children are called parent nodes, the node without a parent is called the root node, while nodes with no children are called leaf nodes.

The level of a node is how far it is below the root node; the height of a node is how far it is above the furthest leaf.

One use of binary trees is efficient searching and sorting (e.g. binary search tree). The properties of trees mean nodes can be found quickly and compared easily, especially for trees which are balanced. (A tree is balanced if and only if the left and right subtrees of every node differ in height by no more than 1).

Types of binary trees

  • Full binary tree
  • Complete binary tree
  • Perfect binary tree
  • Balanced binary tree
  • Degenerate binary tree
  • Root binary tree

Other types

Uses

Useful links

Related tags

6746 questions
395
votes
19 answers

What are the applications of binary trees?

I am wondering what the particular applications of binary trees are. Could you give some real examples?
Jichao
  • 40,341
  • 47
  • 125
  • 198
365
votes
14 answers

Difference between binary tree and binary search tree

Can anyone please explain the difference between binary tree and binary search tree with an example?
Neel
  • 9,913
  • 16
  • 52
  • 74
264
votes
7 answers

Skip List vs. Binary Search Tree

I recently came across the data structure known as a skip list. It seems to have very similar behavior to a binary search tree. Why would you ever want to use a skip list over a binary search tree?
Claudiu
  • 224,032
  • 165
  • 485
  • 680
214
votes
23 answers

How to print binary tree diagram in Java?

How can I print a binary tree in Java so that the output is like: 4 / \ 2 5 My node: public class Node { Node left, right; A data; public Node(A data){ this.data = data; } }
Tian
  • 2,453
  • 5
  • 18
  • 10
212
votes
8 answers

Heap vs Binary Search Tree (BST)

What is the difference between a heap and BST? When to use a heap and when to use a BST? If you want to get the elements in a sorted fashion, is BST better over heap?
kc3
  • 4,281
  • 7
  • 20
  • 16
209
votes
13 answers

Are duplicate keys allowed in the definition of binary search trees?

I'm trying to find the definition of a binary search tree and I keep finding different definitions everywhere. Some say that for any given subtree the left child key is less than or equal to the root. Some say that for any given subtree the right…
Tim Merrifield
  • 6,088
  • 5
  • 31
  • 33
190
votes
34 answers

How to find the lowest common ancestor of two nodes in any binary tree?

The Binary Tree here is may not necessarily be a Binary Search Tree. The structure could be taken as - struct node { int data; struct node *left; struct node *right; }; The maximum solution I could work out with a friend was something…
Siddhant
  • 2,535
  • 4
  • 20
  • 22
180
votes
8 answers

Explain Morris inorder tree traversal without using stacks or recursion

Can someone please help me understand the following Morris inorder tree traversal algorithm without using stacks or recursion ? I was trying to understand how it works, but its just escaping me. 1. Initialize current as root 2. While current is…
brainydexter
  • 19,826
  • 28
  • 77
  • 115
144
votes
7 answers

When to use Preorder, Postorder, and Inorder Binary Search Tree Traversal strategies

I realized recently that while having used BST's plenty in my life, I've never even contemplated using anything but Inorder traversal (while I am aware of and know how easy it is to adapt a program to use pre/post-order traversal). Upon realizing…
John Humphreys
  • 37,047
  • 37
  • 155
  • 255
140
votes
21 answers

How to implement a binary tree?

Which is the best data structure that can be used to implement a binary tree in Python?
Bruce
  • 33,927
  • 76
  • 174
  • 262
117
votes
28 answers

How to determine if binary tree is balanced?

It's been a while from those school years. Got a job as IT specialist at a hospital. Trying to move to do some actual programming now. I'm working on binary trees now, and I was wondering what would be the best way to determine if the tree is…
user69514
  • 26,935
  • 59
  • 154
  • 188
116
votes
34 answers

Find kth smallest element in a binary search tree in Optimum way

I need to find the kth smallest element in the binary search tree without using any static/global variable. How to achieve it efficiently? The solution that I have in my mind is doing the operation in O(n), the worst case since I am planning to do…
bragboy
  • 34,892
  • 30
  • 114
  • 171
116
votes
7 answers

Is Big O(logn) log base e?

For binary search tree type of data structures, I see the Big O notation is typically noted as O(logn). With a lowercase 'l' in log, does this imply log base e (n) as described by the natural logarithm? Sorry for the simple question but I've…
BuckFilledPlatypus
  • 2,108
  • 5
  • 18
  • 23
87
votes
11 answers

With ' N ' no of nodes, how many different Binary and Binary Search Trees possible?

For Binary trees: There's no need to consider tree node values, I am only interested in different tree topologies with 'N' nodes. For Binary Search Tree: We have to consider tree node values.
siva
  • 1,693
  • 2
  • 21
  • 29
87
votes
13 answers

Difference between "Complete binary tree", "strict binary tree","full binary Tree"?

I am confused about the terminology of the below trees, I have been studying the Tree, and I am unable to distinguish between these trees: a) Complete Binary Tree b) Strict Binary Tree c) Full Binary Tree Please help me to differentiate among these…
kTiwari
  • 1,488
  • 1
  • 14
  • 21
1
2 3
…
99 100