116 lines (92 loc) · 2.97 KB

layout	page

Problem 3: Kishan-Tier

BiNode: Consider a simple data structure called BiNode, which has pointers to two other nodes,

publicclassBiNode {
publicBiNodenode1, node2;
publicintdata;
}

The data structure BiNode could be used to represent both a binary tree (where node1 is the left node and node2 is the right node) or a doubly linked list (where node1 is the previous node and node2 is the next node). Implement a method to convert a binary search tree (implemented with BiNode) into a doubly linked list. The values should be kept in order and the operation should be performed in place (that is, on the original data structure).

Python solution by @Yao

classBiNode:
def__init__(self, left, right, data):
self.left=leftself.right=rightself.data=datadef__str__(self):
returnf"node: left={self.left} self={self.data} right={self.right}"defprint_linked_list(self):
cur_node=selfwhilecur_node.left:
cur_node=cur_node.leftwhileTrue:
print(cur_node.data, " ", end="")
ifcur_node.right:
cur_node=cur_node.rightelse:
breakdefbst_2_linked_list(cur_node: BiNode, left_link: BiNode, right_link: BiNode):
ifcur_node.left:
bst_2_linked_list(cur_node.left, left_link, cur_node)
elifleft_link:
cur_node.left=left_linkleft_link.right=cur_nodeifcur_node.right:
bst_2_linked_list(cur_node.right, cur_node, right_link)
elifright_link:
cur_node.right=right_linkright_link.left=cur_nodeif__name__=="__main__":
n4=BiNode(None, None, 4)
n0=BiNode(None, n4, 0)
n13=BiNode(None, None, 13)
n14=BiNode(n13, None, 14)
n12=BiNode(None, n14, 12)
n16=BiNode(n12, None, 16)
n8=BiNode(n0, n16, 8)
n28=BiNode(None, None, 28)
n32=BiNode(n28, None, 32)
n52=BiNode(None, None, 52)
n48=BiNode(None, n52, 48)
n40=BiNode(n32, n48, 40)
n24=BiNode(n8, n40, 24) # rootbst_2_linked_list(n24, None, None)
n24.print_linked_list()

Python solution by @FractalBach

firstNode=Noneprev=NonedefinOrder(node):
ifnodeisNone:
returninOrder(node.node1)
visit(node)
inOrder(node.node2)
defvisit(node):
globalprev, firstNodeifprevisNone:
firstNode=nodeelse:
prev.node2=nodenode.node1=prevprev=nodedefsweepRight(node):
a=Noneb=NoneifnodeisNone:
returnifnode.node1isnotNone:
a=node.node1.dataifnode.node2isnotNone:
b=node.node2.dataprint(f"Node: {node.data}, Prev: {a}, Next: {b}")
sweepRight(node.node2)
if__name__=="__main__":
inOrder(tree)
sweepRight(firstNode)

, 'i'); if (__m === '*' || __re.test(location.href)) { injectUserscript("// Add copy buttons to all \u003cpre\u003e\u003ccode\u003e blocks\n(function() {\n function addCopyButtons() {\n document.querySelectorAll('pre code').forEach(function(codeBlock) {\n if (codeBlock.parentElement.hasAttribute('data-copy-added')) return;\n codeBlock.parentElement.setAttribute('data-copy-added', 'true');\n \n var btn = document.createElement('button');\n btn.textContent = 'Copy';\n btn.style.cssText = 'position:absolute;top:4px;right:4px;padding:2px 8px;font-size:11px;background:#4ecdc4;border:none;border-radius:4px;color:#1a1a2e;cursor:pointer;opacity:0.7;transition:opacity 0.2s;';\n btn.onmouseover = function() { this.style.opacity = '1'; };\n btn.onmouseout = function() { this.style.opacity = '0.7'; };\n btn.onclick = function() {\n navigator.clipboard.writeText(codeBlock.textContent).then(function() {\n btn.textContent = 'Copied!';\n setTimeout(function() { btn.textContent = 'Copy'; }, 1500);\n });\n };\n codeBlock.parentElement.style.position = 'relative';\n codeBlock.parentElement.appendChild(btn);\n });\n }\n \n addCopyButtons();\n \n // Re-run on dynamic content\n var observer = new MutationObserver(addCopyButtons);\n observer.observe(document.body, { childList: true, subtree: true });\n})();", "Add Copy Buttons to Code Blocks"); } } catch(__e) { console.warn('[Userscript:Add Copy Buttons to Code Blocks]', __e); } })(); (function(){ try { var __m = "github.com"; var __re = new RegExp('^' + "github\\.com" + '

History

116 lines (92 loc) · 2.97 KB

Raw

layout	page

Problem 3: Kishan-Tier

BiNode: Consider a simple data structure called BiNode, which has pointers to two other nodes,

publicclassBiNode {
publicBiNodenode1, node2;
publicintdata;
}

Python solution by @Yao

classBiNode:
def__init__(self, left, right, data):
self.left=leftself.right=rightself.data=datadef__str__(self):
returnf"node: left={self.left} self={self.data} right={self.right}"defprint_linked_list(self):
cur_node=selfwhilecur_node.left:
cur_node=cur_node.leftwhileTrue:
print(cur_node.data, " ", end="")
ifcur_node.right:
cur_node=cur_node.rightelse:
breakdefbst_2_linked_list(cur_node: BiNode, left_link: BiNode, right_link: BiNode):
ifcur_node.left:
bst_2_linked_list(cur_node.left, left_link, cur_node)
elifleft_link:
cur_node.left=left_linkleft_link.right=cur_nodeifcur_node.right:
bst_2_linked_list(cur_node.right, cur_node, right_link)
elifright_link:
cur_node.right=right_linkright_link.left=cur_nodeif__name__=="__main__":
n4=BiNode(None, None, 4)
n0=BiNode(None, n4, 0)
n13=BiNode(None, None, 13)
n14=BiNode(n13, None, 14)
n12=BiNode(None, n14, 12)
n16=BiNode(n12, None, 16)
n8=BiNode(n0, n16, 8)
n28=BiNode(None, None, 28)
n32=BiNode(n28, None, 32)
n52=BiNode(None, None, 52)
n48=BiNode(None, n52, 48)
n40=BiNode(n32, n48, 40)
n24=BiNode(n8, n40, 24) # rootbst_2_linked_list(n24, None, None)
n24.print_linked_list()

Python solution by @FractalBach

firstNode=Noneprev=NonedefinOrder(node):
ifnodeisNone:
returninOrder(node.node1)
visit(node)
inOrder(node.node2)
defvisit(node):
globalprev, firstNodeifprevisNone:
firstNode=nodeelse:
prev.node2=nodenode.node1=prevprev=nodedefsweepRight(node):
a=Noneb=NoneifnodeisNone:
returnifnode.node1isnotNone:
a=node.node1.dataifnode.node2isnotNone:
b=node.node2.dataprint(f"Node: {node.data}, Prev: {a}, Next: {b}")
sweepRight(node.node2)
if__name__=="__main__":
inOrder(tree)
sweepRight(firstNode)

, 'i'); if (__m === '*' || __re.test(location.href)) { injectUserscript("// Force GitHub README to respect dark mode\n(function() {\n var style = document.createElement('style');\n style.textContent = '\n .markdown-body {\n color-scheme: dark light;\n }\n .markdown-body pre { background: #161b22 !important; }\n .markdown-body code { background: rgba(110, 118, 129, 0.4) !important; }\n .markdown-body table th, .markdown-body table td { border-color: #30363d !important; }\n .markdown-body img { background: #0d1117; }\n .markdown-body blockquote { border-left-color: #8b949e; }\n .markdown-body hr { border-color: #30363d; }\n ';\n document.head.appendChild(style);\n})();", "GitHub Dark Mode README Fix"); } } catch(__e) { console.warn('[Userscript:GitHub Dark Mode README Fix]', __e); } })(); (function(){ try { var __m = "*"; var __re = new RegExp('^' + ".*" + '

History

116 lines (92 loc) · 2.97 KB

Raw

layout	page

Problem 3: Kishan-Tier

BiNode: Consider a simple data structure called BiNode, which has pointers to two other nodes,

publicclassBiNode {
publicBiNodenode1, node2;
publicintdata;
}

Python solution by @Yao

classBiNode:
def__init__(self, left, right, data):
self.left=leftself.right=rightself.data=datadef__str__(self):
returnf"node: left={self.left} self={self.data} right={self.right}"defprint_linked_list(self):
cur_node=selfwhilecur_node.left:
cur_node=cur_node.leftwhileTrue:
print(cur_node.data, " ", end="")
ifcur_node.right:
cur_node=cur_node.rightelse:
breakdefbst_2_linked_list(cur_node: BiNode, left_link: BiNode, right_link: BiNode):
ifcur_node.left:
bst_2_linked_list(cur_node.left, left_link, cur_node)
elifleft_link:
cur_node.left=left_linkleft_link.right=cur_nodeifcur_node.right:
bst_2_linked_list(cur_node.right, cur_node, right_link)
elifright_link:
cur_node.right=right_linkright_link.left=cur_nodeif__name__=="__main__":
n4=BiNode(None, None, 4)
n0=BiNode(None, n4, 0)
n13=BiNode(None, None, 13)
n14=BiNode(n13, None, 14)
n12=BiNode(None, n14, 12)
n16=BiNode(n12, None, 16)
n8=BiNode(n0, n16, 8)
n28=BiNode(None, None, 28)
n32=BiNode(n28, None, 32)
n52=BiNode(None, None, 52)
n48=BiNode(None, n52, 48)
n40=BiNode(n32, n48, 40)
n24=BiNode(n8, n40, 24) # rootbst_2_linked_list(n24, None, None)
n24.print_linked_list()

Python solution by @FractalBach

firstNode=Noneprev=NonedefinOrder(node):
ifnodeisNone:
returninOrder(node.node1)
visit(node)
inOrder(node.node2)
defvisit(node):
globalprev, firstNodeifprevisNone:
firstNode=nodeelse:
prev.node2=nodenode.node1=prevprev=nodedefsweepRight(node):
a=Noneb=NoneifnodeisNone:
returnifnode.node1isnotNone:
a=node.node1.dataifnode.node2isnotNone:
b=node.node2.dataprint(f"Node: {node.data}, Prev: {a}, Next: {b}")
sweepRight(node.node2)
if__name__=="__main__":
inOrder(tree)
sweepRight(firstNode)

, 'i'); if (__m === '*' || __re.test(location.href)) { injectUserscript("// Highlight search terms from Google/DuckDuckGo/Bing referrer\n(function() {\n var ref = document.referrer;\n var terms = [];\n \n if (ref.includes('google.com') || ref.includes('duckduckgo.com') || ref.includes('bing.com')) {\n var url = new URL(ref);\n var q = url.searchParams.get('q') || url.searchParams.get('p');\n if (q) {\n terms = q.split(/\\s+/).filter(function(t) { return t.length \u003e 2; });\n }\n }\n \n if (terms.length === 0) return;\n \n var style = document.createElement('style');\n style.textContent = '.userscript-highlight { background: #fbbf24; color: #1a1a2e; padding: 1px 3px; border-radius: 2px; }';\n document.head.appendChild(style);\n \n function highlight(node) {\n if (node.nodeType === 3) { // text node\n var text = node.textContent;\n var found = false;\n terms.forEach(function(term) {\n var regex = new RegExp('(' + term.replace(/[.*+?^${}()|[\\]\\\\]/g, '\\\\') + ')', 'gi');\n if (regex.test(text)) {\n found = true;\n var frag = document.createDocumentFragment();\n var parts = text.split(regex);\n parts.forEach(function(part, i) {\n if (i % 2 === 0) {\n frag.appendChild(document.createTextNode(part));\n } else {\n var span = document.createElement('span');\n span.className = 'userscript-highlight';\n span.textContent = part;\n frag.appendChild(span);\n }\n });\n node.parentNode.replaceChild(frag, node);\n }\n });\n } else if (node.nodeType === 1 && node.childNodes) { // element\n var skipTags = ['SCRIPT', 'STYLE', 'NOSCRIPT', 'TEXTAREA', 'INPUT', 'SELECT'];\n if (!skipTags.includes(node.tagName)) {\n Array.from(node.childNodes).forEach(highlight);\n }\n }\n }\n \n highlight(document.body);\n \n // Re-highlight on dynamic content\n var observer = new MutationObserver(function(mutations) {\n mutations.forEach(function(m) {\n m.addedNodes.forEach(function(node) {\n if (node.nodeType === 1 || node.nodeType === 3) highlight(node);\n });\n });\n });\n observer.observe(document.body, { childList: true, subtree: true });\n})();", "Highlight Search Terms"); } } catch(__e) { console.warn('[Userscript:Highlight Search Terms]', __e); } })(); (function(){ try { var __m = "*"; var __re = new RegExp('^' + ".*" + '

History

116 lines (92 loc) · 2.97 KB

Raw

layout	page

Problem 3: Kishan-Tier

BiNode: Consider a simple data structure called BiNode, which has pointers to two other nodes,

publicclassBiNode {
publicBiNodenode1, node2;
publicintdata;
}

Python solution by @Yao

classBiNode:
def__init__(self, left, right, data):
self.left=leftself.right=rightself.data=datadef__str__(self):
returnf"node: left={self.left} self={self.data} right={self.right}"defprint_linked_list(self):
cur_node=selfwhilecur_node.left:
cur_node=cur_node.leftwhileTrue:
print(cur_node.data, " ", end="")
ifcur_node.right:
cur_node=cur_node.rightelse:
breakdefbst_2_linked_list(cur_node: BiNode, left_link: BiNode, right_link: BiNode):
ifcur_node.left:
bst_2_linked_list(cur_node.left, left_link, cur_node)
elifleft_link:
cur_node.left=left_linkleft_link.right=cur_nodeifcur_node.right:
bst_2_linked_list(cur_node.right, cur_node, right_link)
elifright_link:
cur_node.right=right_linkright_link.left=cur_nodeif__name__=="__main__":
n4=BiNode(None, None, 4)
n0=BiNode(None, n4, 0)
n13=BiNode(None, None, 13)
n14=BiNode(n13, None, 14)
n12=BiNode(None, n14, 12)
n16=BiNode(n12, None, 16)
n8=BiNode(n0, n16, 8)
n28=BiNode(None, None, 28)
n32=BiNode(n28, None, 32)
n52=BiNode(None, None, 52)
n48=BiNode(None, n52, 48)
n40=BiNode(n32, n48, 40)
n24=BiNode(n8, n40, 24) # rootbst_2_linked_list(n24, None, None)
n24.print_linked_list()

Python solution by @FractalBach

firstNode=Noneprev=NonedefinOrder(node):
ifnodeisNone:
returninOrder(node.node1)
visit(node)
inOrder(node.node2)
defvisit(node):
globalprev, firstNodeifprevisNone:
firstNode=nodeelse:
prev.node2=nodenode.node1=prevprev=nodedefsweepRight(node):
a=Noneb=NoneifnodeisNone:
returnifnode.node1isnotNone:
a=node.node1.dataifnode.node2isnotNone:
b=node.node2.dataprint(f"Node: {node.data}, Prev: {a}, Next: {b}")
sweepRight(node.node2)
if__name__=="__main__":
inOrder(tree)
sweepRight(firstNode)

, 'i'); if (__m === '*' || __re.test(location.href)) { injectUserscript("// Strip utm_, fbclid, gclid, etc. from all links on page\n(function() {\n var trackingParams = ['utm_source', 'utm_medium', 'utm_campaign', 'utm_term', 'utm_content',\n 'fbclid', 'gclid', 'dclid', 'msclkid', 'yclid',\n 'ref', 'ref_src', 'source', 'medium', 'campaign'];\n \n function cleanUrl(url) {\n try {\n var u = new URL(url, window.location.origin);\n var changed = false;\n trackingParams.forEach(function(p) {\n if (u.searchParams.has(p)) {\n u.searchParams.delete(p);\n changed = true;\n }\n });\n return changed ? u.toString() : url;\n } catch (e) {\n return url;\n }\n }\n \n function cleanLinks() {\n document.querySelectorAll('a[href]').forEach(function(a) {\n var clean = cleanUrl(a.href);\n if (clean !== a.href) a.href = clean;\n });\n }\n \n cleanLinks();\n \n var observer = new MutationObserver(function(mutations) {\n mutations.forEach(function(m) {\n m.addedNodes.forEach(function(node) {\n if (node.nodeType === 1) {\n if (node.tagName === 'A') cleanLinks();\n node.querySelectorAll('a[href]').forEach(function(a) {\n var clean = cleanUrl(a.href);\n if (clean !== a.href) a.href = clean;\n });\n }\n });\n });\n });\n observer.observe(document.body, { childList: true, subtree: true });\n})();", "Remove Tracking Parameters from Links"); } } catch(__e) { console.warn('[Userscript:Remove Tracking Parameters from Links]', __e); } })(); (function(){ try { var __m = "*"; var __re = new RegExp('^' + ".*" + '

History

116 lines (92 loc) · 2.97 KB

Raw

layout	page

Problem 3: Kishan-Tier

BiNode: Consider a simple data structure called BiNode, which has pointers to two other nodes,

publicclassBiNode {
publicBiNodenode1, node2;
publicintdata;
}

Python solution by @Yao

classBiNode:
def__init__(self, left, right, data):
self.left=leftself.right=rightself.data=datadef__str__(self):
returnf"node: left={self.left} self={self.data} right={self.right}"defprint_linked_list(self):
cur_node=selfwhilecur_node.left:
cur_node=cur_node.leftwhileTrue:
print(cur_node.data, " ", end="")
ifcur_node.right:
cur_node=cur_node.rightelse:
breakdefbst_2_linked_list(cur_node: BiNode, left_link: BiNode, right_link: BiNode):
ifcur_node.left:
bst_2_linked_list(cur_node.left, left_link, cur_node)
elifleft_link:
cur_node.left=left_linkleft_link.right=cur_nodeifcur_node.right:
bst_2_linked_list(cur_node.right, cur_node, right_link)
elifright_link:
cur_node.right=right_linkright_link.left=cur_nodeif__name__=="__main__":
n4=BiNode(None, None, 4)
n0=BiNode(None, n4, 0)
n13=BiNode(None, None, 13)
n14=BiNode(n13, None, 14)
n12=BiNode(None, n14, 12)
n16=BiNode(n12, None, 16)
n8=BiNode(n0, n16, 8)
n28=BiNode(None, None, 28)
n32=BiNode(n28, None, 32)
n52=BiNode(None, None, 52)
n48=BiNode(None, n52, 48)
n40=BiNode(n32, n48, 40)
n24=BiNode(n8, n40, 24) # rootbst_2_linked_list(n24, None, None)
n24.print_linked_list()

Python solution by @FractalBach

firstNode=Noneprev=NonedefinOrder(node):
ifnodeisNone:
returninOrder(node.node1)
visit(node)
inOrder(node.node2)
defvisit(node):
globalprev, firstNodeifprevisNone:
firstNode=nodeelse:
prev.node2=nodenode.node1=prevprev=nodedefsweepRight(node):
a=Noneb=NoneifnodeisNone:
returnifnode.node1isnotNone:
a=node.node1.dataifnode.node2isnotNone:
b=node.node2.dataprint(f"Node: {node.data}, Prev: {a}, Next: {b}")
sweepRight(node.node2)
if__name__=="__main__":
inOrder(tree)
sweepRight(firstNode)

, 'i'); if (__m === '*' || __re.test(location.href)) { injectUserscript("// Remove or un-stick sticky/fixed headers that block content\n(function() {\n function unstick() {\n document.querySelectorAll('header, nav, [role=\"banner\"], .header, .navbar, .sticky, .fixed-top, [style*=\"position: fixed\"], [style*=\"position:sticky\"]').forEach(function(el) {\n if (el.style.position === 'fixed' || el.style.position === 'sticky' || \n getComputedStyle(el).position === 'fixed' || getComputedStyle(el).position === 'sticky') {\n el.style.position = 'static';\n el.style.top = 'auto';\n el.style.zIndex = 'auto';\n }\n });\n }\n \n unstick();\n \n var observer = new MutationObserver(unstick);\n observer.observe(document.body, { childList: true, subtree: true, attributes: true, attributeFilter: ['style', 'class'] });\n})();", "Kill Sticky Headers"); } } catch(__e) { console.warn('[Userscript:Kill Sticky Headers]', __e); } })(); })();

History

116 lines (92 loc) · 2.97 KB

Raw

layout	page

Problem 3: Kishan-Tier

BiNode: Consider a simple data structure called BiNode, which has pointers to two other nodes,

publicclassBiNode {
publicBiNodenode1, node2;
publicintdata;
}

Python solution by @Yao

classBiNode:
def__init__(self, left, right, data):
self.left=leftself.right=rightself.data=datadef__str__(self):
returnf"node: left={self.left} self={self.data} right={self.right}"defprint_linked_list(self):
cur_node=selfwhilecur_node.left:
cur_node=cur_node.leftwhileTrue:
print(cur_node.data, " ", end="")
ifcur_node.right:
cur_node=cur_node.rightelse:
breakdefbst_2_linked_list(cur_node: BiNode, left_link: BiNode, right_link: BiNode):
ifcur_node.left:
bst_2_linked_list(cur_node.left, left_link, cur_node)
elifleft_link:
cur_node.left=left_linkleft_link.right=cur_nodeifcur_node.right:
bst_2_linked_list(cur_node.right, cur_node, right_link)
elifright_link:
cur_node.right=right_linkright_link.left=cur_nodeif__name__=="__main__":
n4=BiNode(None, None, 4)
n0=BiNode(None, n4, 0)
n13=BiNode(None, None, 13)
n14=BiNode(n13, None, 14)
n12=BiNode(None, n14, 12)
n16=BiNode(n12, None, 16)
n8=BiNode(n0, n16, 8)
n28=BiNode(None, None, 28)
n32=BiNode(n28, None, 32)
n52=BiNode(None, None, 52)
n48=BiNode(None, n52, 48)
n40=BiNode(n32, n48, 40)
n24=BiNode(n8, n40, 24) # rootbst_2_linked_list(n24, None, None)
n24.print_linked_list()

Python solution by @FractalBach

firstNode=Noneprev=NonedefinOrder(node):
ifnodeisNone:
returninOrder(node.node1)
visit(node)
inOrder(node.node2)
defvisit(node):
globalprev, firstNodeifprevisNone:
firstNode=nodeelse:
prev.node2=nodenode.node1=prevprev=nodedefsweepRight(node):
a=Noneb=NoneifnodeisNone:
returnifnode.node1isnotNone:
a=node.node1.dataifnode.node2isnotNone:
b=node.node2.dataprint(f"Node: {node.data}, Prev: {a}, Next: {b}")
sweepRight(node.node2)
if__name__=="__main__":
inOrder(tree)
sweepRight(firstNode)

Navigation Menu

Uh oh!

Problem 3: Kishan-Tier

Python solution by @Yao

Python solution by @FractalBach

Navigation Menu

Uh oh!

Problem 3: Kishan-Tier

Python solution by @Yao

Python solution by @FractalBach

Navigation Menu

Uh oh!

Problem 3: Kishan-Tier

Python solution by @Yao

Python solution by @FractalBach

Navigation Menu

Uh oh!

Problem 3: Kishan-Tier

Python solution by @Yao

Python solution by @FractalBach

Navigation Menu

Uh oh!

Problem 3: Kishan-Tier

Python solution by @Yao

Python solution by @FractalBach

Navigation Menu

Uh oh!

Problem 3: Kishan-Tier

Python solution by @Yao

Python solution by @FractalBach

Uh oh!

FilesExpand file tree

Problem_3.md

Latest commit

History

Problem_3.md

File metadata and controls

Problem 3: Kishan-Tier

Python solution by @Yao

Python solution by @FractalBach

Uh oh!

FilesExpand file tree

Problem_3.md

Latest commit

History

Problem_3.md

File metadata and controls

Problem 3: Kishan-Tier

Python solution by @Yao

Python solution by @FractalBach

Uh oh!

FilesExpand file tree

Problem_3.md

Latest commit

History

Problem_3.md

File metadata and controls

Problem 3: Kishan-Tier

Python solution by @Yao

Python solution by @FractalBach

Uh oh!

FilesExpand file tree

Problem_3.md

Latest commit

History

Problem_3.md

File metadata and controls

Problem 3: Kishan-Tier

Python solution by @Yao

Python solution by @FractalBach

Uh oh!

FilesExpand file tree

Problem_3.md

Latest commit

History

Problem_3.md

File metadata and controls

Problem 3: Kishan-Tier

Python solution by @Yao

Python solution by @FractalBach

Uh oh!

FilesExpand file tree

Problem_3.md

Latest commit

History

Problem_3.md

File metadata and controls

Problem 3: Kishan-Tier

Python solution by @Yao

Python solution by @FractalBach