Questions tagged [binary-tree]

A high-level data structure, made of nodes, each with a maximum of 2 children (left and right). Nodes with no children are called leaves, and two nodes with the same parent are known as siblings.

Filter by
Sorted by
Tagged with
11 votes
9 answers
1k views

Decide Contiguous Binary Tree

Objective Given an unlabelled binary tree, decide whether it is contiguous in indices. Indices This challenge gives one-indexing on binary trees. The exact definition expresses all indices in binary ...
Dannyu NDos's user avatar
  • 5,639
11 votes
14 answers
703 views

Increasing permutation trees

For this challenge a "binary tree" is a rooted tree where each node has 0 children (leaf) or 2. The children of a node are unordered, meaning that while you might draw the tree with left ...
Wheat Wizard's user avatar
  • 97.8k
28 votes
12 answers
2k views

Rows of the Collatz tree

Consider a binary tree built the following way: The root node is \$1\$ For a given node \$n\$: If \$n\$ is odd, its only child is \$2n\$ If \$n\$ is even, one of its children is \$2n\$. If \$\frac {...
caird coinheringaahin g's user avatar
12 votes
1 answer
253 views

Create Word Lightning

Sandbox Inspired by a Codingame challenge I tried (and failed at) about a month ago. Given a binary tree of words, say: ...
Razetime's user avatar
  • 27k
16 votes
8 answers
285 views

Side to side, not up and down

Task Given a list of nodes representing a binary tree of positive integers serialized depth-first, return a list of nodes representing the same tree serialized breadth-first. To represent an absent ...
user's user avatar
  • 287
4 votes
3 answers
6k views

The Great Battle Conundrum- Who are Alive?

Maximillian is the chief commander of the Great Greek Army and he is leading his forces into a crucial war with Spain. If all the enemy soldiers stand in a straight line incrementally marked starting ...
Pluviophile's user avatar
17 votes
2 answers
692 views

Count unrooted, unlabeled binary trees of n nodes

An unrooted binary tree is an unrooted tree (a graph that has single connected component and contains no cycles) where each vertex has exactly one or three neighbors. It is used in bioinformatics to ...
Bubbler's user avatar
  • 75.2k
20 votes
20 answers
2k views

Fibonacci trees

Background Fibonacci trees \$T_n\$ are a sequence of rooted binary trees of height \$n-1\$. They are defined as follows: \$T_0\$ has no nodes. \$T_1\$ has a single node (the root). The root node of \$...
Bubbler's user avatar
  • 75.2k
8 votes
2 answers
364 views

Deserialize a binary tree breadth-first

Deserializing binary trees depth-first is pretty easy, but doing it breadth-first is (hopefully) harder. Your mission, should you choose to accept it, is to do the latter. The input will be a 1-D list ...
user's user avatar
  • 287
5 votes
8 answers
581 views

Shortest Program To Find Lowest Common Ancestor of Two Nodes in a Binary Tree

Any two separate nodes in a binary tree have a common ancestor, which is the root of a binary tree. The lowest common ancestor(LCA) is thus defined as the node that is furthest from the root and that ...
T. Salim's user avatar
  • 655
17 votes
10 answers
6k views

Write The Shortest Program To Check If A Binary Tree Is Balanced

For each node in a balanced binary tree, the maximum difference in the heights of the left child subtree and the right child subtree are at most 1. The height of a binary tree is the distance from ...
T. Salim's user avatar
  • 655
20 votes
20 answers
7k views

Write The Shortest Program to Calculate Height of a Binary Tree

The height of a binary tree is the distance from the root node to the node child that is farthest from the root. Below is an example: ...
T. Salim's user avatar
  • 655
24 votes
16 answers
2k views

Is this a BST pre-order traversal?

Background A binary tree is a rooted tree whose every node has at most two children. A labelled binary tree is a binary tree whose every node is labelled with a positive integer; moreover, all ...
Delfad0r's user avatar
  • 6,246
17 votes
7 answers
954 views

Binary tree rotations

Balanced binary search trees are essential to guarantee O(log n) lookups (or similar operations). In a dynamic environment where a lot of keys are randomly inserted and/or deleted, trees might ...
ბიმო's user avatar
  • 16.8k
15 votes
12 answers
2k views

Binary Branches

Given a binary number, your task is to create a 'branch' of that number, with a depth of 2. For example, given 0 as input, you should output exactly this: ...
Okx's user avatar
  • 16.4k
20 votes
9 answers
2k views

Enumerate binary trees

Binary trees A binary tree is a tree with nodes of three types: terminal nodes, which have no children unary nodes, which have one child each binary nodes, which have two children each We can ...
Guy Coder's user avatar
  • 321
24 votes
7 answers
942 views

Plant a binary forest!

Inspired by A014486. Challenge Given an integer input in base 10, construct a representation for the binary forest corresponding to the input. Representations include, but are not limited to, nested ...
JungHwan Min's user avatar
  • 13.8k
46 votes
4 answers
3k views

Build an aesthetically pleasing divisor tree

An aesthetically pleasing divisor tree is a tree of divisors of input n that, for any composite number m, has two children nodes ...
Sherlock9's user avatar
  • 12.2k
14 votes
5 answers
679 views

Pre-order + post-order to in-order

Task Given the pre-order and post-order traversals of a full binary tree, return its in-order traversal. The traversals will be represented as two lists, both containing n distinct positive integers,...
Lynn's user avatar
  • 68.2k
8 votes
1 answer
284 views

Tree traversing

Have you heard about trees? When performing DFS on a binary tree, you can traverse it in 3 possible orders. Root, left node, right node (Pre-order) Left node, Root, right node (In-order) Left node, ...
jkklapp's user avatar
  • 106
7 votes
1 answer
436 views

Print a non-clashing binary search tree

Brief Print an ASCII representation of a binary search tree. You should write your own minimum implementation logic of a BST (node, left, right, insert) (50,30,70,20,80,40,75,90) gives: ...
Denham Coote's user avatar
  • 1,437
6 votes
5 answers
5k views

Convert binary search tree into ordered linked list

Write the shortest possible program that turns a binary search tree into an ordered doubly-linked list, by modifying the pointers to the left and the right children of each node. Arguments: a pointer ...
user avatar
9 votes
6 answers
1k views

Find a binary tree's deepest node

Write a program that takes a binary tree as input, and outputs the deepest node and its depth. If there is a tie, print all involved nodes as well as their depths. Each node is represented as: ...
Jwosty's user avatar
  • 3,586
8 votes
6 answers
2k views

Fix your trees!

In informatics, we often use trees in lots of different forms and representations. The three major methods of serialising binary trees are prefix, infix and postfix notation. For example, the ...
tomsmeding's user avatar
  • 2,044
15 votes
12 answers
3k views

Create Balanced BST from Sorted List of Integers

Given a unique, sorted list of integers, create a balanced binary-search tree represented as an array without using recursion. For example: ...
Jake Wharton's user avatar
14 votes
10 answers
2k views

Find a fraction's position in the Stern-Brocot tree

The Stern-Brocot tree is a binary tree of fractions where each fraction is acquired by adding the numerators and denominators of the two fractions neighbouring it in the levels above. It is generated ...
Joe Z.'s user avatar
  • 34.8k
10 votes
8 answers
2k views

Enumerate all binary trees with n nodes

Given an integer n, enumerate all possible full binary trees with n internal nodes. (Full binary trees have exactly 2 children on every internal node). The tree structure should be output as a pre-...
Kyle Butt's user avatar
  • 203
10 votes
5 answers
912 views

Huffman golfing [duplicate]

Write a filter that converts text from standard input to a representation of its Huffman tree on standard output. In as few characters as possible. you're free to consider newlines or not output ...
J B's user avatar
  • 9,944
20 votes
5 answers
6k views

Print a Binary Tree

Inspired by a recent question on SO... Write a function to print a binary tree in the following format: 3 / \ 1 5 \ / \ 2 4 6 The output should ...
Anon.'s user avatar
  • 1,849
14 votes
5 answers
11k views

Free a Binary Tree [closed]

So before you read some basic computer science concepts. A binary tree is a dynamically allocated structure (usually used for ordered storage). Because of its nature traversal of binary trees is ...
Martin York's user avatar