-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathcheck-if-a-tree-is-bst-or-not.html
More file actions
82 lines (73 loc) · 21.7 KB
/
check-if-a-tree-is-bst-or-not.html
File metadata and controls
82 lines (73 loc) · 21.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Algorithm - Check if a tree is BST or not</title>
<meta name="generator" content="VuePress 1.8.2">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="description" content="Algorithm to check if a given binary tree is BST, If a given input tree follows Binary search tree property or not">
<meta property="og:site_name" content="DevTut">
<meta property="og:title" content="Algorithm - Check if a tree is BST or not">
<meta property="og:description" content="Algorithm to check if a given binary tree is BST, If a given input tree follows Binary search tree property or not">
<meta property="og:type" content="article">
<meta property="og:url" content="/algorithm/check-if-a-tree-is-bst-or-not.html">
<meta property="og:image" content="/logo.png">
<meta name="twitter:title" content="Algorithm - Check if a tree is BST or not">
<meta name="twitter:description" content="Algorithm to check if a given binary tree is BST, If a given input tree follows Binary search tree property or not">
<meta name="twitter:url" content="/algorithm/check-if-a-tree-is-bst-or-not.html">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="/logo.png">
<meta name="theme-color" content="#ffffff">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="msapplication-TileImage" content="/mstile-150x150.png">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="google-site-verification" content="76_rKXgwMVIjd-axJC_1zPV9OS4mEjvtgjYOWVkAdnQ">
<link rel="preload" href="/assets/css/0.styles.60619e34.css" as="style"><link rel="preload" href="/assets/js/app.1779e102.js" as="script"><link rel="preload" href="/assets/js/3.2cfa8016.js" as="script"><link rel="preload" href="/assets/js/25.51d5046e.js" as="script">
<link rel="stylesheet" href="/assets/css/0.styles.60619e34.css">
</head>
<body>
<div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">DevTut</span></a> <div class="links"><form id="search-form" role="search" class="algolia-search-wrapper search-box"><input id="algolia-search-input" class="search-query"></form> <nav class="nav-links can-hide"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav> <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>Algorithm</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/algorithm/" aria-current="page" class="sidebar-link">Disclaimer</a></li><li><a href="/algorithm/getting-started-with-algorithm.html" class="sidebar-link">Getting started with algorithm</a></li><li><a href="/algorithm/algorithm-complexity.html" class="sidebar-link">Algorithm Complexity</a></li><li><a href="/algorithm/big-o-notation.html" class="sidebar-link">Big-O Notation</a></li><li><a href="/algorithm/trees.html" class="sidebar-link">Trees</a></li><li><a href="/algorithm/binary-search-trees.html" class="sidebar-link">Binary Search Trees</a></li><li><a href="/algorithm/check-if-a-tree-is-bst-or-not.html" aria-current="page" class="active sidebar-link">Check if a tree is BST or not</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/algorithm/check-if-a-tree-is-bst-or-not.html#algorithm-to-check-if-a-given-binary-tree-is-bst" class="sidebar-link">Algorithm to check if a given binary tree is BST</a></li><li class="sidebar-sub-header"><a href="/algorithm/check-if-a-tree-is-bst-or-not.html#if-a-given-input-tree-follows-binary-search-tree-property-or-not" class="sidebar-link">If a given input tree follows Binary search tree property or not</a></li></ul></li><li><a href="/algorithm/binary-tree-traversals.html" class="sidebar-link">Binary Tree traversals</a></li><li><a href="/algorithm/lowest-common-ancestor-of-a-binary-tree.html" class="sidebar-link">Lowest common ancestor of a Binary Tree</a></li><li><a href="/algorithm/graph.html" class="sidebar-link">Graph</a></li><li><a href="/algorithm/graph-traversals.html" class="sidebar-link">Graph Traversals</a></li><li><a href="/algorithm/dijkstras-algorithm.html" class="sidebar-link">Dijkstra’s Algorithm</a></li><li><a href="/algorithm/a-pathfinding.html" class="sidebar-link">A* Pathfinding</a></li><li><a href="/algorithm/a-pathfinding-algorithm.html" class="sidebar-link">A* Pathfinding Algorithm</a></li><li><a href="/algorithm/dynamic-programming.html" class="sidebar-link">Dynamic Programming</a></li><li><a href="/algorithm/applications-of-dynamic-programming.html" class="sidebar-link">Applications of Dynamic Programming</a></li><li><a href="/algorithm/kruskal-s-algorithm.html" class="sidebar-link">Kruskal's Algorithm</a></li><li><a href="/algorithm/greedy-algorithms.html" class="sidebar-link">Greedy Algorithms</a></li><li><a href="/algorithm/applications-of-greedy-technique.html" class="sidebar-link">Applications of Greedy technique</a></li><li><a href="/algorithm/prim-s-algorithm.html" class="sidebar-link">Prim's Algorithm</a></li><li><a href="/algorithm/bellman-ford-algorithm.html" class="sidebar-link">Bellman–Ford Algorithm</a></li><li><a href="/algorithm/line-algorithm.html" class="sidebar-link">Line Algorithm</a></li><li><a href="/algorithm/floyd-warshall-algorithm.html" class="sidebar-link">Floyd-Warshall Algorithm</a></li><li><a href="/algorithm/catalan-number-algorithm.html" class="sidebar-link">Catalan Number Algorithm</a></li><li><a href="/algorithm/multithreaded-algorithms.html" class="sidebar-link">Multithreaded Algorithms</a></li><li><a href="/algorithm/knuth-morris-pratt-kmp-algorithm.html" class="sidebar-link">Knuth Morris Pratt (KMP) Algorithm</a></li><li><a href="/algorithm/edit-distance-dynamic-algorithm.html" class="sidebar-link">Edit Distance Dynamic Algorithm</a></li><li><a href="/algorithm/online-algorithms.html" class="sidebar-link">Online algorithms</a></li><li><a href="/algorithm/integer-partition-algorithm.html" class="sidebar-link">Integer Partition Algorithm</a></li><li><a href="/algorithm/maximum-path-sum-algorithm.html" class="sidebar-link">Maximum Path Sum Algorithm</a></li><li><a href="/algorithm/maximum-subarray-algorithm.html" class="sidebar-link">Maximum Subarray Algorithm</a></li><li><a href="/algorithm/sliding-window-algorithm.html" class="sidebar-link">Sliding Window Algorithm</a></li><li><a href="/algorithm/sorting.html" class="sidebar-link">Sorting</a></li><li><a href="/algorithm/bubble-sort.html" class="sidebar-link">Bubble Sort</a></li><li><a href="/algorithm/merge-sort.html" class="sidebar-link">Merge Sort</a></li><li><a href="/algorithm/insertion-sort.html" class="sidebar-link">Insertion Sort</a></li><li><a href="/algorithm/bucket-sort.html" class="sidebar-link">Bucket Sort</a></li><li><a href="/algorithm/quicksort.html" class="sidebar-link">Quicksort</a></li><li><a href="/algorithm/counting-sort.html" class="sidebar-link">Counting Sort</a></li><li><a href="/algorithm/heap-sort.html" class="sidebar-link">Heap Sort</a></li><li><a href="/algorithm/cycle-sort.html" class="sidebar-link">Cycle Sort</a></li><li><a href="/algorithm/odd-even-sort.html" class="sidebar-link">Odd-Even Sort</a></li><li><a href="/algorithm/selection-sort.html" class="sidebar-link">Selection Sort</a></li><li><a href="/algorithm/pigeonhole-sort.html" class="sidebar-link">Pigeonhole Sort</a></li><li><a href="/algorithm/radix-sort.html" class="sidebar-link">Radix Sort</a></li><li><a href="/algorithm/shell-sort.html" class="sidebar-link">Shell Sort</a></li><li><a href="/algorithm/pancake-sort.html" class="sidebar-link">Pancake Sort</a></li><li><a href="/algorithm/searching.html" class="sidebar-link">Searching</a></li><li><a href="/algorithm/substring-search.html" class="sidebar-link">Substring Search</a></li><li><a href="/algorithm/breadth-first-search.html" class="sidebar-link">Breadth-First Search</a></li><li><a href="/algorithm/depth-first-search.html" class="sidebar-link">Depth First Search</a></li><li><a href="/algorithm/hash-functions.html" class="sidebar-link">Hash Functions</a></li><li><a href="/algorithm/travelling-salesman.html" class="sidebar-link">Travelling Salesman</a></li><li><a href="/algorithm/shortest-common-supersequence-problem.html" class="sidebar-link">Shortest Common Supersequence Problem</a></li><li><a href="/algorithm/knapsack-problem.html" class="sidebar-link">Knapsack Problem</a></li><li><a href="/algorithm/equation-solving.html" class="sidebar-link">Equation Solving</a></li><li><a href="/algorithm/longest-common-subsequence.html" class="sidebar-link">Longest Common Subsequence</a></li><li><a href="/algorithm/longest-increasing-subsequence.html" class="sidebar-link">Longest Increasing Subsequence</a></li><li><a href="/algorithm/check-two-strings-are-anagrams.html" class="sidebar-link">Check two strings are anagrams</a></li><li><a href="/algorithm/pascal-s-triangle.html" class="sidebar-link">Pascal's Triangle</a></li><li><a href="/algorithm/algo-print-a-m-n-matrix-in-square-wise.html" class="sidebar-link">Algo:- Print a m*n matrix in square wise</a></li><li><a href="/algorithm/matrix-exponentiation.html" class="sidebar-link">Matrix Exponentiation</a></li><li><a href="/algorithm/polynomial-time-bounded-algorithm-for-minimum-vertex-cover.html" class="sidebar-link">polynomial-time bounded algorithm for Minimum Vertex Cover</a></li><li><a href="/algorithm/dynamic-time-warping.html" class="sidebar-link">Dynamic Time Warping</a></li><li><a href="/algorithm/fast-fourier-transform.html" class="sidebar-link">Fast Fourier Transform</a></li><li><a href="/algorithm/pseudocode.html" class="sidebar-link">Pseudocode</a></li><li><a href="/algorithm/contributors.html" class="sidebar-link">The Contributors</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="check-if-a-tree-is-bst-or-not"><a href="#check-if-a-tree-is-bst-or-not" class="header-anchor">#</a> Check if a tree is BST or not</h1> <h2 id="algorithm-to-check-if-a-given-binary-tree-is-bst"><a href="#algorithm-to-check-if-a-given-binary-tree-is-bst" class="header-anchor">#</a> Algorithm to check if a given binary tree is BST</h2> <p>A binary tree is BST if it satisfies any one of the following condition:</p> <ol><li>It is empty</li> <li>It has no subtrees</li> <li>For every node x in the tree all the keys (if any) in the left sub tree must be less than key(x) and all the keys (if any) in the right sub tree must be greater than key(x).</li></ol> <p>So a straightforward recursive algorithm would be:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">is_BST</span><span class="token punctuation">(</span>root<span class="token punctuation">)</span><span class="token operator">:</span>
<span class="token keyword">if</span> root <span class="token operator">==</span> <span class="token constant">NULL</span><span class="token operator">:</span>
<span class="token keyword">return</span> <span class="token boolean">true</span>
<span class="token comment">// Check values in left subtree</span>
<span class="token keyword">if</span> root<span class="token operator">-></span>left <span class="token operator">!=</span> <span class="token constant">NULL</span><span class="token operator">:</span>
max_key_in_left <span class="token operator">=</span> <span class="token function">find_max_key</span><span class="token punctuation">(</span>root<span class="token operator">-></span>left<span class="token punctuation">)</span>
<span class="token keyword">if</span> max_key_in_left <span class="token operator">></span> root<span class="token operator">-></span>key<span class="token operator">:</span>
<span class="token keyword">return</span> <span class="token boolean">false</span>
<span class="token comment">// Check values in right subtree</span>
<span class="token keyword">if</span> root<span class="token operator">-></span>right <span class="token operator">!=</span> <span class="token constant">NULL</span><span class="token operator">:</span>
min_key_in_right <span class="token operator">=</span> <span class="token function">find_min_key</span><span class="token punctuation">(</span>root<span class="token operator">-></span>right<span class="token punctuation">)</span>
<span class="token keyword">if</span> min_key_in_right <span class="token operator"><</span> root<span class="token operator">-></span>key<span class="token operator">:</span>
<span class="token keyword">return</span> <span class="token boolean">false</span>
<span class="token keyword">return</span> <span class="token function">is_BST</span><span class="token punctuation">(</span>root<span class="token operator">-></span>left<span class="token punctuation">)</span> <span class="token operator">&&</span> <span class="token function">is_BST</span><span class="token punctuation">(</span>root<span class="token operator">-></span>right<span class="token punctuation">)</span>
</code></pre></div><p>The above recursive algorithm is correct but inefficient, because it traverses each node mutiple times.</p> <p>Another approach to minimize the multiple visits of each node is to remember the min and max possible values of the keys in the subtree we are visiting. Let the minimum possible value of any key be <code>K_MIN</code> and maximum value be <code>K_MAX</code>. When we start from the root of the tree, the range of values in the tree is <code>[K_MIN,K_MAX]</code>. Let the key of root node be <code>x</code>. Then the range of values in left subtree is <code>[K_MIN,x)</code> and the range of values in right subtree is <code>(x,K_MAX]</code>. We will use this idea to develop a more efficient algorithm.</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">is_BST</span><span class="token punctuation">(</span>root<span class="token punctuation">,</span> min<span class="token punctuation">,</span> max<span class="token punctuation">)</span><span class="token operator">:</span>
<span class="token keyword">if</span> root <span class="token operator">==</span> <span class="token constant">NULL</span><span class="token operator">:</span>
<span class="token keyword">return</span> <span class="token boolean">true</span>
<span class="token comment">// is the current node key out of range?</span>
<span class="token keyword">if</span> root<span class="token operator">-></span>key <span class="token operator"><</span> min <span class="token operator">||</span> root<span class="token operator">-></span>key <span class="token operator">></span> max<span class="token operator">:</span>
<span class="token keyword">return</span> <span class="token boolean">false</span>
<span class="token comment">// check if left and right subtree is BST</span>
<span class="token keyword">return</span> <span class="token function">is_BST</span><span class="token punctuation">(</span>root<span class="token operator">-></span>left<span class="token punctuation">,</span>min<span class="token punctuation">,</span>root<span class="token operator">-></span>key<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">&&</span> <span class="token function">is_BST</span><span class="token punctuation">(</span>root<span class="token operator">-></span>right<span class="token punctuation">,</span>root<span class="token operator">-></span>key<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>max<span class="token punctuation">)</span>
</code></pre></div><p>It will be initially called as:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">is_BST</span><span class="token punctuation">(</span>my_tree_root<span class="token punctuation">,</span>KEY_MIN<span class="token punctuation">,</span>KEY_MAX<span class="token punctuation">)</span>
</code></pre></div><p>Another approach will be to do inorder traversal of the Binary tree. If the inorder traversal produces a sorted sequence of keys then the given tree is a BST. To check if the inorder sequence is sorted remember the value of previously visited node and compare it against the current node.</p> <h2 id="if-a-given-input-tree-follows-binary-search-tree-property-or-not"><a href="#if-a-given-input-tree-follows-binary-search-tree-property-or-not" class="header-anchor">#</a> If a given input tree follows Binary search tree property or not</h2> <p>For example</p> <p><strong>if the input is:</strong></p> <p><a href="https://i.stack.imgur.com/sd2Zq.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/sd2Zq.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p><strong>Output should be false:</strong></p> <p>As 4 in the left sub-tree is greater than the root value(3)</p> <p><strong>If the input is:</strong></p> <p><a href="https://i.stack.imgur.com/GR41M.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/GR41M.png" alt="enter image description here"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p><strong>Output should be true</strong></p></div> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/devtut/generate/edit/master/docs/algorithm/check-if-a-tree-is-bst-or-not.md" target="_blank" rel="noopener noreferrer">Edit this page on GitHub</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
←
<a href="/algorithm/binary-search-trees.html" class="prev">
Binary Search Trees
</a></span> <span class="next"><a href="/algorithm/binary-tree-traversals.html">
Binary Tree traversals
</a>
→
</span></p></div> </main></div><div class="global-ui"><!----></div></div>
<script src="/assets/js/app.1779e102.js" defer></script><script src="/assets/js/3.2cfa8016.js" defer></script><script src="/assets/js/25.51d5046e.js" defer></script>
</body>
</html>